home *** CD-ROM | disk | FTP | other *** search
/ PCMania 64 / PCMania CD64_1.iso / phy / phy004 / websel / graphics.faq next >
Encoding:
Internet Message Format  |  1997-05-22  |  94.6 KB
  1. From: orourke@cs.smith.edu (Joseph O'Rourke)
  2. Newsgroups: comp.graphics.algorithms,news.answers,comp.answers
  3. Subject: comp.graphics.algorithms Frequently Asked Questions
  4. Message-ID: <graphics/algorithms-faq-1-863680082@cs.smith.edu>
  5. Reply-To: orourke@cs.smith.edu (Joseph O'Rourke)
  6. Followup-To: comp.graphics.algorithms
  7. Distribution: world
  8. Approved: news-answers-request@MIT.EDU
  9. Expires: 05/30/97 03:08:02 EDT
  10. Supersedes: <graphics/algorithms-faq-1-862470482@cs.smith.edu>
  11. Keywords: faq computer graphics algorithms geometry
  12. X-Content-Currency: This FAQ changes regularly. See item (0.03) for instructions
  13.    on how to obtain a new copy via FTP.
  14. Originator: orourke@grendel.csc.smith.edu
  15. NNTP-Posting-Host: grendel.csc.smith.edu
  16. Date: 15 May 97 07:07:41 GMT
  17. Organization: Smith College, Northampton Mass, USA
  18. Lines: 2254
  19. Path: news.uv.es!news.rediris.es!minerva.ibernet.es!uunet!in1.uu.net!206.154.70.8!news.webspan.net!feed1.news.erols.com!cpk-news-hub1.bbnplanet.com!cam-news-feed5.bbnplanet.com!news.bbnplanet.com!umass.edu!news.smith.edu!orourke
  20. Xref: news.uv.es comp.graphics.algorithms:48925 news.answers:12827 comp.answers:24554
  21. Status: N
  22.  
  23. Posted-By: auto-faq 3.2.1.4
  24. Archive-name: graphics/algorithms-faq
  25. Posting-Frequency: bi-weekly
  26.  
  27.  
  28. Welcome to the FAQ for comp.graphics.algorithms!
  29.  
  30. Thanks to all who have contributed.  Corrections and contributions
  31. (to orourke@cs.smith.edu) always welcome.
  32.  
  33.   Changed items this posting (|): 0.04, 7.02
  34.   New     items this posting (+): none
  35.  
  36. ----------------------------------------------------------------------
  37. Table of Contents
  38. ----------------------------------------------------------------------
  39.  
  40. 0. General Information
  41.    0.01: Charter of comp.graphics.algorithms
  42.    0.02: Are the postings to comp.graphics.algorithms archived?
  43.    0.03: How can I get this FAQ?
  44. |  0.04: What are some must-have books on graphics algorithms?
  45.    0.05: Are there any online references?
  46.    0.06: Are there other graphics related FAQs?
  47.    0.07: Where is all the source?
  48.  
  49. 1. 2D Computations: Points, Segments, Circles, Etc.
  50.    1.01: How do I rotate a 2D point?
  51.    1.02: How do I find the distance from a point to a line?
  52.    1.03: How do I find intersections of 2 2D line segments?
  53.    1.04: How do I generate a circle through three points?
  54.    1.05: Where can I find graph layout algorithms?
  55.  
  56. 2. 2D Polygon Computations
  57.    2.01: How do I find the area of a polygon?
  58.    2.02: How can the centroid of a polygon be computed?
  59.    2.03: How do I find if a point lies within a polygon?
  60.    2.04: How do I find the intersection of two convex polygons?
  61.    2.05: How do I do a hidden surface test (backface culling) with 2d points?
  62.    2.06: How do I find a single point inside a simple polygon?
  63.    2.07: How do I find the orientation of a simple polygon?
  64.  
  65. 3. 2D Image/Pixel Computations
  66.    3.01: How do I rotate a bitmap?
  67.    3.02: How do I display a 24 bit image in 8 bits?
  68.    3.03: How do I fill the area of an arbitrary shape?
  69.    3.04: How do I find the 'edges' in a bitmap?
  70.    3.05: How do I enlarge/sharpen/fuzz a bitmap?
  71.    3.06: How do I map a texture on to a shape?
  72.    3.07: How do I detect a 'corner' in a collection of points?
  73.    3.08: Where do I get source to display (raster font format)?
  74.    3.09: What is morphing/how is it done?
  75.    3.10: How do I quickly draw a filled triangle?
  76.    3.11: D Noise functions and turbulence in Solid texturing.
  77.    3.12: How do I generate realistic sythetic textures?
  78.    3.13: How do I convert between color models (RGB, HLS, CMYK, CIE etc)?
  79.  
  80. 4. Curve Computations
  81.    4.01: How do I generate a bezier curve that is parallel to another bezier?
  82.    4.02: How do I split a bezier at a specific value for t?
  83.    4.03: How do I find a t value at a specific point on a bezier?
  84.    4.04: How do I fit a bezier curve to a circle?
  85.  
  86. 5. 3D computations
  87.    5.01: How do I rotate a 3D point?
  88.    5.02: What is ARCBALL and where is the source?
  89.    5.03: How do I clip a polygon against a rectangle?
  90.    5.04: How do I clip a polygon against another polygon?
  91.    5.05: How do I find the intersection of a line and a plane?
  92.    5.06: How do I determine the intersection between a ray and a polygon?
  93.    5.07: How do I determine the intersection between a ray and a sphere?
  94.    5.08: How do I find the intersection of a ray and a bezier surface?
  95.    5.09: How do I ray trace caustics?
  96.    5.10: What is the marching cubes algorithm?
  97.    5.11: What is the status of the patent on the "marching cubes" algorithm?
  98.    5.12: How do I do a hidden surface test (backface culling) with 3d points?
  99.    5.13: Where can I find algorithms for 3D collision detection?
  100.    5.14: How do I perform basic viewing in 3d?
  101.    5.15: How do I optimize a 3D polygon mesh?
  102.    5.16: How can I perform volume rendering?
  103.    5.17: Where can I get the spline description of the famous teapot etc.?
  104.    5.18: How can the distance between two lines in space be computed?
  105.  
  106. 6. Geometric Structures and Mathematics
  107.    6.01: Where can I get source for Voronoi/Delaunay triangulation?
  108.    6.02: Where do I get source for convex hull?
  109.    6.03: Where do I get source for halfspace intersection?
  110.    6.04: What are barycentric coordinates?
  111.    6.05: How do I generate a random point inside a triangle?
  112.    6.06: How do I evenly distribute N points on (tesselate) a sphere?
  113.    6.07: What are coordinates for the vertices of an icosohedron?
  114.    6.08: How do I generate random points on the surface of a sphere?
  115.  
  116. 7. Contributors
  117.    7.01: How can you contribute to this FAQ?
  118.    7.02: Contributors.  Who made this all possible.
  119.  
  120. Search e.g. for "Section 6" to find that section.
  121. Search e.g. for "Subject 6.04" to find that item.
  122. ----------------------------------------------------------------------
  123. Section 0. General Information
  124. ----------------------------------------------------------------------
  125. Subject 0.01: Charter of comp.graphics.algorithms
  126.  
  127.     comp.graphics.algorithms is an unmoderated newsgroup intended as a forum
  128.     for the discussion of the algorithms used in the process of generating
  129.     computer graphics.  These algorithms may be recently proposed in
  130.     published journals or papers, old or previously known algorithms, or
  131.     hacks used incidental to the process of computer graphics.  The scope of
  132.     these algorithms may range from an efficient way to multiply matrices,
  133.     all the way to a global illumination method incorporating raytracing,
  134.     radiosity, infinite spectrum modeling, and perhaps even mirrored balls
  135.     and lime jello.
  136.  
  137.     It is hoped that this group will serve as a forum for programmers and
  138.     researchers to exchange ideas and ask questions on recent papers or
  139.     current research related to computer graphics.
  140.  
  141.     comp.graphics.algorithms is not:
  142.  
  143.      - for requests for gifs, or other pictures
  144.      - for requests for image translator or processing software; see
  145.             alt.binaries.pictures* FAQ  
  146.             alt.binaries.pictures.utilities (picture source code)
  147.             alt.graphics.pixutils (image format translation)
  148.             comp.sources.misc (image viewing source code)
  149.             sci.image.processing
  150.             comp.graphics.apps.softimage
  151.             fj.comp.image
  152.      - for requests for compression software; for these try:
  153.             alt.comp.compression
  154.             comp.compression
  155.             comp.compression.research
  156.  
  157. ----------------------------------------------------------------------
  158. Subject 0.02: Are the postings to comp.graphics.algorithms archived?
  159.  
  160.     Archives may be found at:
  161.  
  162.       ftp://wuarchive.wustl.edu/graphics/graphics/mail-lists/comp.graphics.algorithms
  163.  
  164.     It is archived in the same manner that all other newsgroups are
  165.     being archived there, namely there is an Index file with all the
  166.     subjects, and all the articles are being kept in a hierarchy based
  167.     on the year and month they are posted.
  168.  
  169.  
  170. ----------------------------------------------------------------------
  171. Subject 0.03: How can I get this FAQ?
  172.  
  173.     Here are a few locations that have the FAQ:
  174.  
  175.       ftp://rtfm.mit.edu/pub/usenet-by-group/news.answers/graphics/algorithms-faq
  176.       ftp://ftp.seas.gwu.edu/pub/rtfm/comp/graphics/algorithms/comp.graphics.algorithms_Frequently_Asked_Questions
  177.       http://www.cis.ohio-state.edu/hypertext/faq/usenet/graphics/algorithms-faq/faq.html
  178.  
  179.     The (busy) rtfm.mit.edu site lists many alternative "mirror" sites.
  180.     The ohio-state site is often out of date.
  181.     Also can reach the FAQ from http://www.geom.umn.edu/software/cglist/,
  182.     which is worth visiting in its own right.
  183.  
  184. ----------------------------------------------------------------------
  185. |Subject 0.04: What are some must-have books on graphics algorithms?
  186.  
  187.     The keywords in brackets are used to refer to the books in later
  188.     questions.  They generally refer to the first author except where
  189.     it is necessary to resolve ambiguity or in the case of the Gems.
  190.  
  191.  
  192.     Basic computer graphics, rendering algorithms,
  193.     ----------------------------------------------
  194.  
  195.     [Foley]
  196.     Computer Graphics: Principles and Practice (2nd Ed.),
  197.     J.D. Foley, A. van Dam, S.K. Feiner, J.F. Hughes, Addison-Wesley
  198.     1990, ISBN 0-201-12110-7
  199.  
  200.     [Rogers:Procedural]
  201.     Procedural Elements for Computer Graphics,
  202.     David F. Rogers, McGraw Hill 1985, ISBN 0-07-053534-5
  203.  
  204.     [Rogers:Mathematical]
  205.     Mathematical Elements for Computer Graphics 2nd Ed.,
  206.     David F. Rogers and J. Alan Adams, McGraw Hill 1990, ISBN
  207.     0-07-053530-2
  208.  
  209.     [Watt:3D]
  210.     _3D Computer Graphics, 2nd Edition_,
  211.     Alan Watt, Addison-Wesley 1993, ISBN 0-201-63186-5
  212.  
  213.     [Glassner:RayTracing]
  214.     An Introduction to Ray Tracing,
  215.     Andrew Glassner (ed.), Academic Press 1989, ISBN 0-12-286160-4
  216.  
  217.     [Gems I]
  218.     Graphics Gems,
  219.     Andrew Glassner (ed.), Academic Press 1990, ISBN 0-12-286165-5
  220.  
  221.     [Gems II]
  222.     Graphics Gems II,
  223.     James Arvo (ed.), Academic Press 1991, ISBN 0-12-64480-0
  224.  
  225.     [Gems III]
  226.     Graphics Gems III,
  227.     David Kirk (ed.), Academic Press 1992, ISBN 0-12-409670-0 (with
  228.     IBM disk) or 0-12-409671-9 (with Mac disk)
  229.     See also "AP Professional Graphics CD-ROM Library,"
  230.     Academic Press,  ISBN 0-12-059756-X, which contains Gems I-III.
  231.  
  232.     [Gems IV]
  233.     Graphics Gems IV,
  234.     Paul S. Heckbert (ed.), Academic Press 1994, ISBN 0-12-336155-9
  235.     (with IBM disk) or 0-12-336156-7 (with Mac disk)
  236.  
  237.     [Gems V]
  238.     Graphic Gems V,
  239.     Alan W. Paeth (ed.), Academic Press 1995, ISBN 0-12-543455-3
  240.     (with IBM disk)
  241.  
  242.     [Watt:Animation]
  243.     Advanced Animation and Rendering Techniques,
  244.     Alan Watt, Mark Watt, Addison-Wesley 1992, ISBN 0-201-54412-1
  245.  
  246.     [Bartels]
  247.     An Introduction to Splines for Use in Computer Graphics and
  248.         Geometric Modeling,
  249.     Richard H. Bartels, John C. Beatty, Brian A. Barsky, 1987, ISBN
  250.     0-934613-27-3
  251.  
  252.     [Farin]
  253.     Curves and Surfaces for Computer Aided Geometric Design:
  254.     A Practical Guide, 3rd Edition, Gerald E. Farin, Academic Press
  255.     1993. ISBN 0-12-249052-5
  256.  
  257.     [Prusinkiewicz]
  258.     The Algorithmic Beauty of Plants,
  259.     Przemyslaw W. Prusinkiewicz, Aristid Lindenmayer, Springer-Verlag,
  260.     1990, ISBN 0-387-97297-8, ISBN 3-540-97297-8
  261.  
  262.     [Oliver]
  263.     Tricks of the Graphics Gurus,
  264.     Dick Oliver, et al. (2) 3.5 PC disks included, $39.95 SAMS Publishing
  265.  
  266.     [Hearn]
  267.     Introduction to computer graphics,
  268.     Hearn & Baker
  269.  
  270.     [Cohen]
  271.     Radiosity and Realistic Imange Sythesis,
  272.     Michael F. Cohen, John R. Wallace, Academic Press Professional
  273.     1993, ISBN 0-12-178270-0
  274.  
  275.     [Ebert]
  276.     Texturing and Modeling - A Procedural Approach
  277.     David S. Ebert (ed.), F. Kenton Musgrave, Darwyn Peachey, Ken Perlin,
  278.         Setven Worley, Academic Press 1994, ISBN 0-12-228760-6,
  279.         ISBN 0-12-2278761-4 (IBM disk)
  280.  
  281.     [Schroeder]
  282.     Visualization Toolkit, The: An Object-Oriented Approach to 3-D
  283.     Graphics (Bk/CD) (Professional Description)
  284.     William J. Schroeder,  Kenneth Martin and Bill Lorensen,
  285.     Prentice-Hall 1996, ISBN: 0-13-199837-4 (Published: 02/02/96)
  286.     See Subject 0.07 for source.
  287.  
  288.     [Anderson]
  289.     PC Graphics Unleashed
  290.     Scott Anderson. SAMS Publishing, ISBN 0-672-30570-4
  291.  
  292. |   Ammeraal, L. (1992) Programming Principles in Computer Graphics,
  293. |   2nd Edition, Chichester: John Wiley, ISBN 0 471 93128 4.
  294.  
  295.     For image processing,
  296.     ---------------------
  297.  
  298.     [Barnsley]
  299.     Fractal Image Compression,
  300.     Michael F. Barnsley and Lyman P. Hurd, AK Peters, Ltd, 1993 ISBN
  301.     1-56881-000-8
  302.  
  303.     [Jain]
  304.     Fundamentals of Image Processing,
  305.     Anil K. Jain, Prentice-Hall 1989, ISBN 0-13-336165-9
  306.  
  307.     [Castleman]
  308.     Digital Image Processing,
  309.     Kenneth R. Castleman, Prentice-Hall 1996, ISBN(Cloth): 0-13-211467-4
  310.     (Description and errata at: "http://www.phoenix.net/~castlman")
  311.  
  312.     [Pratt]
  313.     Digital Image Processing, Second Edition,
  314.     William K. Pratt, Wiley-Interscience 1991, ISBN 0-471-85766-1
  315.  
  316.     [Gonzalez]
  317.     Digital Image Processing (3rd Ed.),
  318.     Rafael C. Gonzalez, Paul Wintz, Addison-Wesley 1992, ISBN
  319.     0-201-50803-6
  320.  
  321.     [Russ]
  322.     The Image Processing Handbook,
  323.     John C. Russ, CRC Press 1992, ISBN 0-8493-4233-3
  324.  
  325.     [Wolberg]
  326.     Digital Image Warping,
  327.     George Wolberg, IEEE Computer Society Press Monograph 1990, ISBN
  328.     0-8186-8944-7
  329.  
  330.  
  331.     Computational geometry,
  332.     ----------------------
  333.  
  334.     [Bowyer]
  335.     A Programmer's Geometry,
  336.     Adrian Bowyer, John Woodwark, Butterworths 1983, 
  337.     ISBN 0-408-01242-0 Pbk
  338.  
  339.     [O' Rourke]
  340.     Computational Geometry in C,
  341.     Joseph O'Rourke, Cambridge University Press 1994, 
  342.     ISBN 0-521-44592-2 Pbk, ISBN 0-521-44034-3 Hdbk
  343.  
  344.     [Samet:Application]
  345.     Applications of Spatial Data Structures:  Computer Graphics, 
  346.     Image Processing, and GIS, 
  347.     Hanan Samet, Addison-Wesley, Reading, MA, 1990.
  348.     ISBN 0-201-50300-0.
  349.  
  350.     [Samet:Design & Analysis]
  351.     The Design and Analysis of Spatial Data Structures,
  352.     Hanan Samet, Addison-Wesley, Reading, MA, 1990.
  353.     ISBN 0-201-50255-0.
  354.  
  355.     [Mortenson]
  356.     Geometric Modeling,
  357.     Michael E. Mortenson, Wiley 1985, ISBN 0-471-88279-8
  358.  
  359.     [Preparata]
  360.     Computational Geometry: An Introduction,
  361.     Franco P. Preparata, Michael Ian Shamos, Springer-Verlag 1985,
  362.     ISBN 0-387-96131-3
  363.  
  364.     [Okabe]
  365.     Spatial Tessellations: Concepts and Applications of Voronoi Diagrams,
  366.     A. Okabe and B. Boots and K. Sugihara,
  367.     John Wiley, Chichester, England, 1992.
  368.  
  369.     Solid Modelling
  370.     ---------------
  371.  
  372.     [Mantyla]
  373.     Introduction to Solid Modeling
  374.     Martti Mantyla, Computer Science Press 1988,
  375.     ISBN 07167-8015-1
  376.  
  377. ----------------------------------------------------------------------
  378. Subject 0.05: Are there any online references?
  379.  
  380.     The computational geometry community maintains its own
  381.     bibliography of publications in or closely related to that
  382.     subject.  Every four months, additions and corrections are
  383.     solicited from users, after which the database is updated and
  384.     released anew.  As of February 1996, it contained 7,154 bib-tex
  385.     entries.  It can be retrieved from
  386.  
  387.     ftp://ftp.cs.usask.ca/pub/geometry/geombib.tar.Z - bibliography proper
  388.  
  389.     ftp://ftp.cs.usask.ca/pub/geometry/geom.ps.Z     - PostScript format
  390.  
  391.     ftp://ftp.cs.usask.ca/pub/geometry/o-cgc19.ps.Z  - overview published
  392.         in '93 in SIGACT News and the Internat. J. Comput.  Geom. Appl.
  393.  
  394.     ftp://ftp.cs.usask.ca/pub/geometry/ftp-hints     - detailed retrieval info
  395.  
  396.     The ACM SIGGRAPH Online Bibliography Project, by
  397.     Stephen Spencer (biblio@siggraph.org).
  398.     The database is available for anonymous FTP from the
  399.     ftp://siggraph.org/publications/bibliography directory.  Please
  400.     download and examine the file READ_ME in that directory for more
  401.     specific information concerning the database.
  402.  
  403.     'netlib' is a useful source for algorithms, member inquiries for
  404.     SIAM, and bibliographic searches.  For information, send mail to
  405.     netlib@ornl.gov, with "send index" in the body of the mail
  406.     message.
  407.  
  408.     You can also find free sources for numerical computation in C via
  409.     ftp://usc.edu/pub/C-numanal.  In particular, grab
  410.     numcomp-free-c.gz in that directory.
  411.  
  412.     Check out Nick Fotis's computer graphics resources FAQ -- it's
  413.     packed with pointers to all sorts of great computer graphics
  414.     stuff.  This FAQ is posted biweekly to comp.graphics.
  415.  
  416.     This WWW page contains links to a large number
  417.     of computer graphic related pages:
  418.     http://www.dataspace.com:84/vlib/comp-graphics.html
  419.  
  420.     There's a Computer Science Bibliography Server at:
  421.     http://glimpse.cs.arizona.edu:1994/bib/
  422.     with Computer Graphics, Vision and Radiosity sections
  423.  
  424.     A comprehensive bibliography of color quantization papers and articles is
  425.     available at ftp://hobbes.lbl.gov/pub/doc/cquant95.txt
  426.  
  427.     Modelling physically based systems for animation:
  428.     http://www.cc.gatech.edu/gvu/animation/Animation.html
  429.  
  430.     The University of Manchester NURBS Library:
  431.     ftp://unix.hensa.ac.uk/pub/misc/unix/nurbs/
  432.  
  433.     For an implementation of Seidel's algorithm for fast trapezoidation
  434.     and triangulation of polygons. You can get the code from:
  435.     ftp://ftp.cs.unc.edu/pub/users/narkhede/triangulation.tar.gz
  436.  
  437.     Ray tracing bibliography:
  438.     ftp://ftp.eye.com/pub/graphics/papers/rtbib95.tar.Z
  439.     ftp://ftp.eye.com/pub/graphics/papers/rtbib95.zip
  440.  
  441.     Quaternions and other comp sci curiosities:
  442.     ftp://ftp.netcom.com/pub/hb/hbaker/hakmem/hakmem.html
  443.  
  444.     Directory of Computational Geometry Software,
  445.     collected by Nina Amenta (nina@geom.umn.edu)
  446.     Nina Amenta is maintaining a WWW directory to computational 
  447.     geometry software. The directory lives at The Geometry Center. 
  448.     It has pointers to lots of convex hull and voronoi diagram programs, 
  449.     triangulations, collision detection, polygon intersection, smallest 
  450.     enclosing ball of a point set and other stuff.
  451.     http://www.geom.umn.edu/software/cglist/lowdvod.html
  452.  
  453.     A compact reference for real-time 3d computer graphics programming:
  454.     http://www.cs.mcgill.ca/~zed
  455.  
  456. ----------------------------------------------------------------------
  457. Subject 0.06: Are there other graphics related FAQs?
  458.  
  459.     BSP Tree FAQ by Bretton Wade
  460.         http://reality.sgi.com/bspfaq/
  461.  
  462.     Gamma and Color FAQs by Charles A. Poynton has
  463.         ftp://ftp.inforamp.net/pub/users/poynton/doc/colour/
  464.         http://www.inforamp.net/~poynton/
  465.  
  466.     The documents are mirrored to space provided by Fraunhofer Computer
  467.     Graphics in Rhode Island, U.S.A. at
  468.         ftp://elaine.crcg.edu/pub/doc/colour/
  469.     in Darmstadt, Germany at
  470.         ftp://ftp.igd.fhg.de/pub/doc/colour/
  471.  
  472. ----------------------------------------------------------------------
  473. Subject 0.07: Where is all the source?
  474.  
  475.     Graphics Gems source code.
  476.     http://www.acm.org/tog/GraphicsGems/
  477.     This site is now the offical distribution site for Graphics Gems code.
  478.  
  479.     General 'stuff'
  480.     ftp://wuarchive.wustl.edu/graphics/graphics
  481.  
  482.     There are a number of interesting items in
  483.     http://theory.lcs.mit.edu/~seth including:
  484.     - Code for 2D Voronoi, Delaunay, and Convex hull
  485.     - Mike Hoymeyer's implementation of Raimund Seidel's
  486.       O( d! n ) time linear programming algorithm for
  487.       n constraints in d dimensions
  488.     - geometric models of UC Berkeley's new computer science
  489.       building
  490.  
  491.     You can find useful overviews of a number of computer graphic
  492.     topics in http://archpropplan.auckland.ac.nz/People/Paul/Paul.html
  493.     including:
  494.     - area/orientation of polygons
  495.     - finding if a point lies within a polygon
  496.     - generating a circle through 3 points
  497.     - description and psuedo-code for Delaunay triangulation
  498.     - basic viewing in 3D
  499.       etc.
  500.  
  501.     Sources to "Computational Geometry in C", by J. O'Rourke
  502.     can be found at ftp://grendel.csc.smith.edu/pub/compgeom
  503.  
  504.     Greg Ferrar has uploaded his heavily commented C++ 3D rendering
  505.     library at ftp://ftp.math.ohio-state.edu/pub/users/gregt
  506.  
  507.     TAGL is a portable and extensible library that provides a subset
  508.     of Open-GL functionalities.
  509.     ftp://sunsite.unc.edu/pub/packages/programming/graphics/tagl21.tgz
  510.  
  511.     Try ftp://x2ftp.oulu.fi  for /pub/msdos/programming/docs/graphpro.lzh by
  512.     Michael Abrash. His XSharp package has an implementation of Xiaoulin
  513.     Wu's anti-aliasing algorithm (in C).
  514.  
  515.     Example sources for BSP tree algorithms can be found in
  516.     ftp://ftp.qualia.com/pub/bspfaq/
  517.  
  518.     Mel Slater (mel@dcs.qmw.ac.uk) also made some implementations of
  519.     BSP trees and shadows for static scenes using shadow volumes
  520.     code available
  521.     http://www.dcs.qmw.ac.uk/~mel/BSP.html
  522.     ftp://ftp.dcs.qmw.ac.uk/people/mel/BSP
  523.  
  524.     The Visualization Toolkit (A visualization textbook, C++ library 
  525.     and Tcl-based interpreter) (see [Schroeder]): 
  526.     http://iuinfo.tuwien.ac.at:8000/htdocs/vtk/
  527.  
  528.     See also 5.17: 
  529.         Where can I get the spline description of the famous teapot etc.?
  530.  
  531. ----------------------------------------------------------------------
  532. Section 1. 2D Computations: Points, Segments, Circles, Etc.
  533. ----------------------------------------------------------------------
  534. Subject 1.01: How do I rotate a 2D point?
  535.  
  536.     In 2-D, the 2x2 matrix is very simple.  If you want to rotate a
  537.     column vector v by t degrees using matrix M, use
  538.  
  539.         M = {{cos t, -sin t}, {sin t, cos t}} in M*v.
  540.  
  541.     If you have a row vector, use the transpose of M (turn rows into
  542.     columns and vice versa).  If you want to combine rotations, in 2-D
  543.     you can just add their angles, but in higher dimensions you must
  544.     multiply their matrices.
  545.  
  546.  
  547. ----------------------------------------------------------------------
  548. Subject 1.02: How do I find the distance from a point to a line?
  549.  
  550.  
  551.     Let the point be C (XC,YC) and the line be AB (XA,YA) to (XB,YB).
  552.     The length of the line segment AB is L:
  553.  
  554.         L=((XB-XA)**2+(YB-YA)**2)**0.5
  555.  
  556.     and
  557.             (YA-YC)(YA-YB)-(XA-XC)(XB-XA)
  558.         r = -----------------------------
  559.                         L**2
  560.  
  561.             (YA-YC)(XB-XA)-(XA-XC)(YB-YA)
  562.         s = -----------------------------
  563.                         L**2
  564.  
  565.     Let I be the point of perpendicular projection of C onto AB, the
  566.  
  567.         XI=XA+r(XB-XA)
  568.         YI=YA+r(YB-YA)
  569.  
  570.     Distance from A to I = r*L
  571.     Distance from C to I = s*L
  572.  
  573.     If r<0      I is on backward extension of AB
  574.     If r>1      I is on ahead extension of AB
  575.     If 0<=r<=1  I is on AB
  576.  
  577.     If s<0      C is left of AB (you can just check the numerator)
  578.     If s>0      C is right of AB
  579.     If s=0      C is on AB
  580.  
  581.  
  582. ----------------------------------------------------------------------
  583. Subject 1.03: How do I find intersections of 2 2D line segments?
  584.  
  585.     This problem can be extremely easy or extremely difficult depends
  586.     on your applications.  If all you want is the intersection point,
  587.     the following should work:
  588.  
  589.     Let A,B,C,D be 2-space position vectors.  Then the directed line
  590.     segments AB & CD are given by:
  591.  
  592.         AB=A+r(B-A), r in [0,1]
  593.         CD=C+s(D-C), s in [0,1]
  594.  
  595.     If AB & CD intersect, then
  596.  
  597.         A+r(B-A)=C+s(D-C), or
  598.  
  599.         XA+r(XB-XA)=XC+s(XD-XC)
  600.         YA+r(YB-YA)=YC+s(YD-YC)  for some r,s in [0,1]
  601.  
  602.     Solving the above for r and s yields
  603.  
  604.             (YA-YC)(XD-XC)-(XA-XC)(YD-YC)
  605.         r = -----------------------------  (eqn 1)
  606.             (XB-XA)(YD-YC)-(YB-YA)(XD-XC)
  607.  
  608.             (YA-YC)(XB-XA)-(XA-XC)(YB-YA)
  609.         s = -----------------------------  (eqn 2)
  610.             (XB-XA)(YD-YC)-(YB-YA)(XD-XC)
  611.  
  612.     Let I be the position vector of the intersection point, then
  613.  
  614.         I=A+r(B-A) or
  615.  
  616.         XI=XA+r(XB-XA)
  617.         YI=YA+r(YB-YA)
  618.  
  619.     By examining the values of r & s, you can also determine some
  620.     other limiting conditions:
  621.  
  622.         If 0<=r<=1 & 0<=s<=1, intersection exists
  623.             r<0 or r>1 or s<0 or s>1 line segments do not intersect
  624.  
  625.         If the denominator in eqn 1 is zero, AB & CD are parallel
  626.         If the numerator in eqn 1 is also zero, AB & CD are coincident
  627.  
  628.     If the intersection point of the 2 lines are needed (lines in this
  629.     context mean infinite lines) regardless whether the two line
  630.     segments intersect, then
  631.  
  632.         If r>1, I is located on extension of AB
  633.         If r<0, I is located on extension of BA
  634.         If s>1, I is located on extension of CD
  635.         If s<0, I is located on extension of DC
  636.  
  637.     Also note that the denominators of eqn 1 & 2 are identical.
  638.  
  639.     References:
  640.  
  641.     [O'Rourke] pp. 249-51
  642.     [Gems III] pp. 199-202 "Faster Line Segment Intersection,"
  643.  
  644.  
  645. ----------------------------------------------------------------------
  646. Subject 1.04: How do I generate a circle through three points?
  647.  
  648.     Let the three given points be a, b, c.  Use _0 and _1 to represent
  649.     x and y coordinates. The coordinates of the center p=(p_0,p_1) of
  650.     the circle determined by a, b, and c are:
  651.  
  652.         A = b_0 - a_0;
  653.         B = b_1 - a_1;
  654.         C = c_0 - a_0;
  655.         D = c_1 - a_1;
  656.     
  657.         E = A*(a_0 + b_0) + B*(a_1 + b_1);
  658.         F = C*(a_0 + c_0) + D*(a_1 + c_1);
  659.     
  660.         G = 2.0*(A*(c_1 - b_1)-B*(c_0 - b_0));
  661.     
  662.         p_0 = (D*E - B*F) / G;
  663.         p_1 = (A*F - C*E) / G;
  664.  
  665.     If G is zero then the three points are collinear and no finite-radius
  666.     circle through them exists.  Otherwise, the radius of the circle is:
  667.  
  668.             r^2 = (a_0 - p_0)^2 + (a_1 - p_1)^2
  669.  
  670.     Reference:
  671.  
  672.     [O' Rourke] p. 201. Simplified by Jim Ward.
  673.  
  674. ----------------------------------------------------------------------
  675. Subject 1.05: Where can I find graph layout algorithms?
  676.  
  677.     See the paper by Eades and Tamassia, "Algorithms for Drawing
  678.     Graphs: An Annotated Bibliography," Tech Rep CS-89-09, Dept.  of
  679.     CS, Brown Univ, Feb. 1989.
  680.  
  681.     A revised version of the annotated bibliography on graph drawing
  682.     algorithms by Giuseppe Di Battista, Peter Eades, and Roberto
  683.     Tamassia is now available from
  684.  
  685.     ftp://wilma.cs.brown.edu/pub/papers/compgeo/gdbiblio.tex.gz and
  686.     ftp://wilma.cs.brown.edu/pub/papers/compgeo/gdbiblio.ps.gz
  687.  
  688.  
  689. ----------------------------------------------------------------------
  690. Section 2. 2D Polygon Computations
  691. ----------------------------------------------------------------------
  692. Subject 2.01: How do I find the area of a polygon?
  693.  
  694.     The signed area can be computed in linear time by a simple sum.
  695.     The key formula is this:
  696.  
  697.         If the coordinates of vertex v_i are x_i and y_i,
  698.         twice the signed area of a polygon is given by
  699.  
  700.         2 A( P ) = sum_{i=0}^{n-1} (x_i y_{i+1} - y_i x_{i+1}).
  701.  
  702.     Here n is the number of vertices of the polygon.
  703.     References: [O' Rourke] pp. 18-27; [Gems II] pp. 5-6:
  704.     "The Area of a Simple Polygon", Jon Rokne.
  705.  
  706.     To find the area of a planar polygon not in the x-y plane, use:
  707.     
  708.        2 A(P) = abs(N . (sum_{i=0}^{n-1} (v_i x v_{i+1})))
  709.     
  710.        where N is a unit vector normal to the plane. The `.' represents the
  711.        dot product operator, the `x' represents the cross product operator,
  712.        and abs() is the absolute value function.
  713.     
  714.     [Gems II] pp. 170-171:
  715.     "Area of Planar Polygons and Volume of Polyhedra", Ronald N. Goldman.
  716.  
  717. ----------------------------------------------------------------------
  718. Subject 2.02: How can the centroid of a polygon be computed?
  719.  
  720.     The centroid (a.k.a. the center of mass, or center of gravity)
  721.     of a polygon can be computed as the weighted sum of the centroids
  722.     of a partition of the polygon into triangles.  The centroid of a
  723.     triangle is simply the average of its three vertices, i.e., it
  724.     has coordinates (x1 + x2 + x3)/3 and (y1 + y2 + y3)/3.  This 
  725.     suggests first triangulating the polygon, then forming a sum
  726.     of the centroids of each triangle, weighted by the area of
  727.     each triangle, the whole sum normalized by the total polygon area.
  728.     This indeed works, but there is a simpler method:  the triangulation
  729.     need not be a partition, but rather can use positively and
  730.     negatively oriented triangles (with positive and negative areas),
  731.     as is used when computing the area of a polygon.  This leads to
  732.     a very simple algorithm for computing the centroid, based on a
  733.     sum of triangle centroids weighted with their signed area.
  734.     The triangles can be taken to be those formed by one fixed vertex
  735.     v0 of the polygon, and the two endpoints of consecutive edges of
  736.     the polygon: (v1,v2), (v2,v3), etc.  The area of a triangle with
  737.     vertices a, b, c is half of this expression:
  738.                 (b[X] - a[X]) * (c[Y] - a[Y]) -
  739.                 (c[X] - a[X]) * (b[Y] - a[Y]);
  740.  
  741.     Code available at ftp://grendel.csc.smith.edu/pub/code/centroid.c (3K).
  742.     Reference: [Gems IV] pp.3-6; also includes code.
  743.  
  744. ----------------------------------------------------------------------
  745. Subject 2.03: How do I find if a point lies within a polygon?
  746.  
  747.     The definitive reference is "Point in Polyon Strategies" by
  748.     Eric Haines [Gems IV]  pp. 24-46.
  749.     The code in the Sedgewick book Algorithms (2nd Edition, p.354) is 
  750.     incorrect.
  751.  
  752.     The essence of the ray-crossing method is as follows.
  753.     Think of standing inside a field with a fence representing the polygon. 
  754.     Then walk north. If you have to jump the fence you know you are now 
  755.     outside the poly. If you have to cross again you know you are now 
  756.     inside again; i.e., if you were inside the field to start with, the total 
  757.     number of fence jumps you would make will be odd, whereas if you were 
  758.     ouside the jumps will be even.
  759.  
  760.     The code below is from Wm. Randolph Franklin <wrf@ecse.rpi.edu>
  761.     with some minor modifications for speed.
  762.  
  763.     int pnpoly(int npol, float *xp, float *yp, float x, float y)
  764.     {
  765.       int i, j, c = 0;
  766.       for (i = 0, j = npol-1; i < npol; j = i++) {
  767.         if ((((yp[i]<=y) && (y<yp[j])) ||
  768.              ((yp[j]<=y) && (y<yp[i]))) &&
  769.             (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
  770.  
  771.           c = !c;
  772.       }
  773.       return c;
  774.     }
  775.  
  776.     References:
  777.     [Gems IV]  pp. 24-46
  778.     [O'Rourke] pp. 233-238
  779.     [Glassner:RayTracing]
  780.  
  781. ----------------------------------------------------------------------
  782. Subject 2.04: How do I find the intersection of two convex polygons?
  783.  
  784.     Unlike intersections of general polygons, which might produce a
  785.     quadratic number of pieces, intersection of convex polygons of n
  786.     and m vertices always produces a polygon of at most (n+m) vertices.
  787.     There are a variety of algorithms whose time complexity is proportional
  788.     to this size, i.e., linear.  The first, due to Shamos and Hoey, is
  789.     perhaps the easiest to understand.  Let the two polygons be P and
  790.     Q.  Draw a horizontal line through every vertex of each.  This
  791.     partitions each into trapezoids (with at most two triangles, one
  792.     at the top and one at the bottom).  Now scan down the two polygons
  793.     in concert, one trapezoid at a time, and intersect the trapezoids
  794.     if they overlap vertically.
  795.        A more difficult-to-describe algorithm is in [O'Rourke], pp. 242-252.
  796.     This walks around the boundaries of P and Q in concert, intersecting
  797.     edges.  An implementation is included in [O'Rourke].
  798.  
  799.  
  800. ----------------------------------------------------------------------
  801. Subject 2.05: How do I do a hidden surface test (backface culling) with 2d points?
  802.  
  803.     c = (x1-x2)*(y3-y2)-(y1-y2)*(x3-x2)
  804.  
  805.     x1,y1, x2,y2, x3,y3 = the first three points of the polygon.
  806.  
  807.     If c is positive the polygon is visible. If c is negative the
  808.     polygon is invisible (or the other way).
  809.  
  810.  
  811. ----------------------------------------------------------------------
  812. Subject 2.06: How do I find a single point inside a simple polygon?
  813.  
  814.    Given a simple polygon, find some point inside it.  Here is a method
  815.    based on the proof that there exists an internal diagonal, in
  816.    [O'Rourke, 13-14].  The idea is that the midpoint of a diagonal
  817.    is interior to the polygon.
  818.  
  819.    1. Identify a convex vertex v; let its adjacent vertices be a and b.
  820.    2. For each other vertex q do:
  821.        2a. If q is inside avb, compute distance to v (orthogonal to ab).
  822.        2b. Save point q if distance is a new min.
  823.    3. If no point is inside, return midpoint of ab, or centroid of avb.
  824.    4. Else if some point inside, qv is internal: return its midpoint.
  825.  
  826.    Code for finding a diagonal is in [O'Rourke, 35-39], and is part
  827.    of many other software packages.  See Subject 0.07: Where is all the 
  828.    source?
  829.  
  830. ----------------------------------------------------------------------
  831. Subject 2.07: How do I find the orientation of a simple polygon?
  832.  
  833.     Compute the signed area (Subject 2.01).  The orientation is 
  834.     counter-clockwise if this area is positive.  
  835.  
  836.     A slightly faster method is based on the observation that it isn't
  837.     necessary to compute the area.  One can find the lowest, rightmost
  838.     point of the polygon, and then take the cross product of the edges
  839.     fore and aft of it.  Both methods are O(n) for n vertices, but it
  840.     does seem a waste to add up the total area when a single cross
  841.     product (of just the right edges) suffices.  Code for this is
  842.     available at ftp://grendel.csc.smith.edu/pub/code/polyorient.C (2K).
  843.  
  844.     The reason that the lowest, rightmost point works is that the
  845.     internal angle at this vertex is necessarily convex, strictly less
  846.     than pi (even if there are several equally-lowest points).
  847.  
  848. ----------------------------------------------------------------------
  849. Section 3. 2D Image/Pixel Computations
  850. ----------------------------------------------------------------------
  851. Subject 3.01: How do I rotate a bitmap?
  852.  
  853.     The easiest way, according to the comp.graphics faq, is to take
  854.     the rotation transformation and invert it. Then you just iterate
  855.     over the destination image, apply this inverse transformation and
  856.     find which source pixel to copy there.
  857.  
  858.     A much nicer way comes from the observation that the rotation
  859.     matrix:
  860.  
  861.         R(T) = { { cos(T), -sin(T) }, { sin(T), cos(T) } }
  862.  
  863.     is formed my multiplying three matrices, namely:
  864.  
  865.         R(T) = M1(T) * M2(T) * M3(T)
  866.  
  867.     where
  868.  
  869.         M1(T) = { { 1, -tan(T/2) },
  870.                   { 0, 1         } }
  871.         M2(T) = { { 1,      0    },
  872.                   { sin(T), 1    } }
  873.         M3(T) = { { 1, -tan(T/2) },
  874.                   { 0,         1 } }
  875.  
  876.     Each transformation can be performed in a separate pass, and
  877.     because these transformations are either row-preserving or
  878.     column-preserving, anti-aliasing is quite easy.
  879.  
  880.     Reference:
  881.  
  882.     Paeth, A. W., "A Fast Algorithm for General Raster Rotation",
  883.     Proceedings Graphics Interface '89, Canadian Information
  884.     Processing Society, 1986, 77-81
  885.     [Note - e-mail copies of this paper are no longer available]
  886.  
  887.     [Gems I]
  888.  
  889.  
  890.  
  891. ----------------------------------------------------------------------
  892. Subject 3.02: How do I display a 24 bit image in 8 bits?
  893.  
  894.     [Gems I] pp. 287-293, "A Simple Method for Color Quantization:
  895.     Octree Quantization"
  896.  
  897.     B. Kurz.  Optimal Color Quantization for Color Displays.
  898.     Proceedings of the IEEE Conference on Computer Vision and Pattern
  899.     Recognition, 1983, pp. 217-224.
  900.  
  901.     [Gems II] pp. 116-125, "Efficient Inverse Color Map Computation"
  902.  
  903.         This describes an efficient technique to
  904.         map actual colors to a reduced color map,
  905.         selected by some other technique described
  906.         in the other papers.
  907.  
  908.     [Gems II] pp. 126-133, "Efficient Statistical Computations for
  909.     Optimal Color Quantization"
  910.  
  911.     Xiaolin Wu.  Color Quantization by Dynamic Programming and
  912.     Principal Analysis.  ACM Transactions on Graphics, Vol. 11, No. 4,
  913.     October 1992, pp 348-372.
  914.  
  915.  
  916. ----------------------------------------------------------------------
  917. Subject 3.03: How do I fill the area of an arbitrary shape?
  918.  
  919.  
  920.     "A Fast Algorithm for the Restoration of Images Based on Chain
  921.         Codes Description and Its Applications", L.W. Chang & K.L. Leu,
  922.         Computer Vision, Graphics, and Image Processing, vol.50,
  923.         pp296-307 (1990)
  924.  
  925.     "An Introductory Course in Computer Graphics" by Richard Kingslake,
  926.         (2nd edition) published by Chartwell-Bratt ISBN 0-86238-284-X
  927.  
  928.     [Gems I]
  929.     [Foley]
  930.     [Hearn]
  931.  
  932.  
  933. ----------------------------------------------------------------------
  934. Subject 3.04: How do I find the 'edges' in a bitmap?
  935.  
  936.     A simple method is to put the bitmap through the filter:
  937.  
  938.         -1    -1    -1
  939.         -1     8    -1
  940.         -1    -1    -1
  941.  
  942.     This will highlight changes in contrast.  Then any part of the
  943.     picture where the absolute filtered value is higher than some
  944.     threshold is an "edge".
  945.  
  946.     A more appropriate edge detector for noisy images is
  947.     described by Van Vliet et al. "A nonlinear Laplace operator
  948.     as edge detector in noisy images", in Computer Vision,
  949.     Graphics, and image processing 45, pp. 167-195, 1989.
  950.  
  951.  
  952. ----------------------------------------------------------------------
  953. Subject 3.05: How do I enlarge/sharpen/fuzz a bitmap?
  954.  
  955.     Sharpening of bitmaps can be done by the following algorithm:
  956.  
  957.     I_enh(x,y) = I_fuz(x,y)-k*Laplace(I_fuz(x,y))
  958.  
  959.     or in words:  An image can be sharpened by subtracting a positive
  960.     fraction k of the Laplace from the fuzzy image.
  961.  
  962.     The Laplace is the kernal:
  963.         1   1   1
  964.         1  -8   1
  965.         1   1   1
  966.  
  967.  
  968.     The following library implements Fast Guassian Blurs:
  969.  
  970.     MAGIC: An Object-Oriented Library for Image Analysis by David Eberly
  971.  
  972.     The library source code and the documentation (in Latex) are  at
  973.     ftp://ftp.cs.unc.edu/pub/users/eberly/magic.
  974.     The code compiles on Unix systems using g++ and on PCs using
  975.     Microsoft Windows 3.1 and Borland C++.  The fast Gaussian blurring
  976.     is based on a finite difference method for solving s u_s = s^2 \nabla^2 u
  977.     where s is the standard deviation of the Gaussian (t = s^2/2).  It
  978.     takes advantage of geometrically increasing steps in s (rather than
  979.     linearly increasing steps in t), thus getting to a larger "time" rapidly,
  980.     but still retaining stability.  Section 4.5 of the  documentation contains
  981.     the algorithm description and implementation.
  982.  
  983.      A bitmap is a sampled image, a special case of a digital signal,
  984.      and suffers from two limitations common to all digital signals.
  985.      First, it cannot provide details at fine enough spacing to exactly
  986.      reproduce every continuous image, nor even more detailed sampled
  987.      images. And second, each sample approximates the infinitely fine
  988.      variability of ideal values with a discrete set of ranges encoded
  989.      in a small number of bits---sometimes just one bit per pixel. Many
  990.      times bitmaps have another limitation imposed: The values canot be
  991.      negative. The resolution limitation is perhaps most important.
  992.  
  993.      The ideal way to enlarge a bitmap is to work from the original
  994.      continuous image, magnifying and resampling it. The standard way
  995.      to do it in practice is to (conceptually) reconstruct a continuous
  996.      image from the bitmap, and magnify and resample that instead. This
  997.      will not give the same results, since details of the original have
  998.      already been lost, but it is the best approach possible given an
  999.      already sampled image. More details are provided below.
  1000.  
  1001.      Both sharpening and fuzzing are examples of filtering. Even more
  1002.      specifically, they can be both be accomplished with filters which
  1003.      are linear and shift invariant. A crude way to sharpen along a row
  1004.      (or column) is to set output pixel B[n] to the difference of input
  1005.      pixels, A[n]-A[n-1]. A similarly crude way to fuzz is to set B[n]
  1006.      to the average of input pixels, 1/2*A[n]+1/2*A[n-1]. In each case
  1007.      the output is a weighted sum of input pixels, a "convolution". One
  1008.      important characteristic of such filters is that a sinusoid going
  1009.      in produces a sinusoid coming out, one of the same frequency. Thus
  1010.      the Fourier transform, which decomposes a signal into sinusoids of
  1011.      various frequencies, is the key to analysis of these filters. The
  1012.      simplest (and most efficient) way to handle the two dimensions of
  1013.      images is to operate on first the rows then the columns (or vice
  1014.      versa). Fourier transforms and many filters allow this separation.
  1015.  
  1016.      A filter is linear if it satisfies two simple relations between the
  1017.      input and output: scaling the input by a factor scales the output
  1018.      by the same factor, and the sum of two inputs gives the sum of the
  1019.      two outputs. A filter is shift invariant if shifting the input up,
  1020.      down, left, or right merely shifts the output the same way. When a
  1021.      filter is both linear and shift invariant, it can be implemented as
  1022.      a convolution, a weighted sum. If you find the output of the filter
  1023.      when the input is a single pixel with value one in a sea of zeros,
  1024.      you will know all the weights. This output is the impulse response
  1025.      of the filter. The Fourier transform of the impulse response gives
  1026.      the frequency response of the filter. The pattern of weights read
  1027.      off from the impulse response gives the filter kernel, which will
  1028.      usually be displayed (for image filters) as a 2D stencil array, and
  1029.      it is almost always symmetric around the center. For example, the
  1030.      following filter, approximating a Laplacian (and used for detecting
  1031.      edges), is centered on the negative value.
  1032.              1/6     4/6     1/6
  1033.              4/6   -20/6     4/6
  1034.              1/6     4/6     1/6
  1035.      The symmetry allows a streamlined implementation. Suppose the input
  1036.      image is in A, and the output is to go into B. Then compute
  1037.          B[i][j] = (A[i-1][j-1]+A[i-1][j+1]+A[i+1][j-1]+A[i+1][j+1]
  1038.                     +4.0*(A[i-1][j]+A[i][j-1]+A[i][j+1]+A[i+1][j])
  1039.                     -20.0*A[i][j])/6.0
  1040.  
  1041.      Ideal blurring is uniform in all directions, in other words it has
  1042.      circular symmetry. Gaussian blurs are popular, but the obvious code
  1043.      is slow for wide blurs. A cheap alternative is the following filter
  1044.      (written for rows, but then applied to the columns as well).
  1045.          B[i][j] = ((A[i][j]*2+A[i][j-1]+A[i][j+1])*4
  1046.                      +A[i][j-1]+A[i][j+1]-A[i][j-3]-A[i][j+3])/16
  1047.      For sharpening, subtract the results from the original image, which
  1048.      is equivalent to using the following.
  1049.          B[i][j] = ((A[i][j]*2-A[i][j-1]-A[i][j+1])*4
  1050.                      -A[i][j-1]-A[i][j+1]+A[i][j-3]+A[i][j+3])/16
  1051.      Credit for this filter goes to Ken Turkowski and Steve Gabriel.
  1052.  
  1053.      Reconstruction is impossible without some assumptions, and because
  1054.      of the importance of sinusoids in filtering it is traditional to
  1055.      assume the continuous image is made of sinusoids mixed together.
  1056.      That makes more sense for sounds, where signal processing began,
  1057.      than it does for images, especially computer images of character
  1058.      shapes, sharp surface features, and halftoned shading. As pointed
  1059.      out above, often image values cannot be negative, unlike sinusoids.
  1060.      Also, real world images contain noise. The best noise suppressors
  1061.      (and edge detectors) are, ironically, nonlinear filters.
  1062.  
  1063.      The simplest way to double the size of an image is to use each of
  1064.      the original pixels twice in its row and in its column. For much
  1065.      better results, try this instead. Put zeros between the original
  1066.      pixels, then use the blurring filter given a moment ago. But you
  1067.      might want to divide by 8 instead of 16 (since the zeros will dim
  1068.      the image otherwise). To instead shrink the image by half (in both
  1069.      vertical and horizontal), first apply the filter (dividing by 16),
  1070.      then throw away every other pixel. Notice that there are obvious
  1071.      optimizations involving arithmetic with powers of two, zeros which
  1072.      are in known locations, and pixels which will be discarded.
  1073.  
  1074. ----------------------------------------------------------------------
  1075. Subject 3.06: How do I map a texture on to a shape?
  1076.  
  1077.     Paul S. Heckbert, "Survey of Texture Mapping", IEEE Computer
  1078.     Graphics and Applications V6, #11, Nov. 1986, pp 56-67 revised
  1079.     from Graphics Interface '86 version
  1080.  
  1081.     Eric A. Bier and Kenneth R. Sloan, Jr., "Two-Part Texture
  1082.     Mappings", IEEE Computer Graphics and Applications V6 #9, Sept.
  1083.     1986, pp 40-53 (projection parameterizations)
  1084.  
  1085.  
  1086. ----------------------------------------------------------------------
  1087. Subject 3.07: How do I detect a 'corner' in a collection of points?
  1088.  
  1089.     For the general solution to the problem get Ata Etemadi's software
  1090.     package and associated  papers from one of the addresses below.
  1091.     It's very fast and detects polygons too.
  1092.  
  1093.     The Object Recognition Tookit:
  1094.     http://www2.team17.com/~aetemadi/archive.html
  1095.  
  1096. ----------------------------------------------------------------------
  1097. Subject 3.08: Where do I get source to display (raster font format)?
  1098.  
  1099.     ftp://oak.oakland.edu/SimTel/msdos/graphics
  1100.  
  1101. ----------------------------------------------------------------------
  1102. Subject 3.09: What is morphing/how is it done?
  1103.  
  1104.     See [Anderson], Chapter 3, page 59 - 90.
  1105.  
  1106. ----------------------------------------------------------------------
  1107. Subject 3.10: How do I quickly draw a filled triangle?
  1108.  
  1109.     The easiest way is to render each line separately into an edge
  1110.     buffer. This buffer is a structure which looks like this (in C):
  1111.  
  1112.         struct { int xmin, xmax; } edgebuffer[YDIM];
  1113.  
  1114.     There is one entry for each scan line on the screen, and each
  1115.     entry is to be interpreted as a horizontal line to be drawn from
  1116.     xmin to xmax.
  1117.  
  1118.     Since most people who ask this question are trying to write fast
  1119.     games on the PC, I'll tell you where to find code.  Look at:
  1120.  
  1121.         ftp::/ftp.uwp.edu/pub/msdos/demos/programming/source
  1122.         ftp::/ftp.luth.se/pub/msdos/demos (Sweden)
  1123.         ftp::/NCTUCCCA.edu.tw:/PC/uwp/demos
  1124.         http://www.wit.com:/mirrors/uwp/pub/msdos/demos
  1125.         ftp::/ftp.cdrom.com:/demos
  1126.  
  1127.  
  1128.  
  1129. ----------------------------------------------------------------------
  1130. Subject 3.11: 3D Noise functions and turbulence in Solid texturing.
  1131.  
  1132.     See:
  1133.         ftp://gondwana.ecr.mu.oz.au/pub/siggraph92_C23.shar
  1134.         ftp://ftp.cis.ohio-state.edu/siggraph92/siggraph92_C23.shar
  1135.  
  1136.     In it there are implementations of Perlin's noise and turbulence
  1137.     functions, (By the man himself) as well as Lewis' sparse
  1138.     convolution noise function (by D. Peachey) There is also some of
  1139.     other stuff in there (Musgrave's Earth texture functions, and some
  1140.     stuff on animating gases by Ebert).
  1141.  
  1142.     SPD (Standard Procedural Databases) package:
  1143.         ftp://avalon.chinalake.navy.mil/utils/SPD/SPD33f4.tar.Z
  1144.         ftp://avalon.chinalake.navy.mil/utils/SPD/spd33f4.zip.
  1145.         Now moved to http://www.viewpoint.com/
  1146.  
  1147.  
  1148.     References:
  1149.  
  1150.     [Ebert]
  1151.     Noise, Hypertexture, Antialiasing and Gesture, (Ken Perlin) in
  1152.     Chapter 6, (p.193-), The disk accompanying the book is available
  1153.     from
  1154.         ftp://archive.cs.umbc.edu/pub/texture.
  1155.  
  1156.     For more info on this text/code see:
  1157.         http://www.cs.umbc.edu/~ebert/book/book.html
  1158.  
  1159.     For examples from a current course based on this book, see:
  1160.         http://www.seas.gwu.edu/graphics/ProcTexCourse/
  1161.  
  1162.  
  1163.     [Watt:Animation]
  1164.     Three-dimensional Nocie, Chapter 7.2.1
  1165.     Simulating turbulance, Chapter 7.2.2
  1166.  
  1167. ----------------------------------------------------------------------
  1168. Subject 3.12: How do I generate realistic sythetic textures?
  1169.  
  1170.     For fractal mountains, trees and sea-shells:
  1171.  
  1172.       SPD (Standard Procedural Databases) package:
  1173.         ftp://avalon.chinalake.navy.mil/utils/SPD/SPD33f4.tar.Z
  1174.         ftp://avalon.chinalake.navy.mil/utils/SPD/spd33f4.zip.
  1175.         Now moved to http://www.viewpoint.com/
  1176.  
  1177.  
  1178.  
  1179.     Reaction-Diffusion Algorithms:
  1180.       For an illustartion of the parameter space of a reaction
  1181.       diffusion system, check out the Xmorphia page at
  1182.         http://www.ccsf.caltech.edu/ismap/image.html
  1183.  
  1184.  
  1185.     References:
  1186.  
  1187.     [Ebert]
  1188.     Entire book devoted to this subject, with RenderMan(TM) and C code.
  1189.  
  1190.     [Watt:Animation]
  1191.     Procedural texture mapping and modelling, Chapter 7
  1192.  
  1193.     "Generating Textures on Arbitrary Surfaces Using Reaction-Diffusion"
  1194.      Greg Turk,   Computer Graphics, Vol. 25, No. 4, pp. 289-298
  1195.      July 1991 (SIGGRAPH '91)
  1196.         http://www.cs.unc.edu:80/~turk/reaction_diffusion/reaction_diffusion.html
  1197.  
  1198.     A list of procedural texture synthesis related web pages
  1199.          http://www.threedgraphics.com/pixelloom/tex_synth.html
  1200.  
  1201. ----------------------------------------------------------------------
  1202. Subject 3.13: How do I convert between color models (RGB, HLS, CMYK, CIE etc)?
  1203.  
  1204.     References:
  1205.     [Watt:3D] pp. 313-354
  1206.     [Foley]   pp. 563-603
  1207.  
  1208. ----------------------------------------------------------------------
  1209. Section 4. Curve Computations
  1210. ----------------------------------------------------------------------
  1211. Subject 4.01: How do I generate a bezier curve that is parallel to another bezier?
  1212.  
  1213.     You can't.  The only case where this is possible is when the
  1214.     bezier can be represented by a straight line.  And then the
  1215.     parallel 'bezier' can also be represented by a straight line.
  1216.  
  1217.  
  1218. ----------------------------------------------------------------------
  1219. Subject 4.02: How do I split a bezier at a specific value for t?
  1220.  
  1221.     A Bezier curve is a parametric polynomial function from the
  1222.     interval [0..1] to a space, usually 2-D or 3-D.  Common Bezier
  1223.     curves use cubic polynomials, so have the form
  1224.  
  1225.         f(t) = a3 t^3 + a2 t^2 + a1 t + a0,
  1226.  
  1227.     where the coefficients are points in 3-D. Blossoming converts this
  1228.     polynomial to a more helpful form.  Let s = 1-t, and think of
  1229.     tri-linear interpolation:
  1230.  
  1231.         F([s0,t0],[s1,t1],[s2,t2]) =
  1232.             s0(s1(s2 c30 + t2 c21) + t1(s2 c21 + t2 c12)) +
  1233.             t0(s1(s2 c21 + t2 c12) + t1(s2 c12 + t2 c03))
  1234.             =
  1235.             c30(s0 s1 s2) +
  1236.             c21(s0 s1 t2 + s0 t1 s2 + t0 s1 s2) +
  1237.             c12(s0 t1 t2 + t0 s1 t2 + t0 t1 s2) +
  1238.             c03(t0 t1 t2).
  1239.  
  1240.     The data points c30, c21, c12, and c03 have been used in such a
  1241.     way as to make the resulting function give the same value if any
  1242.     two arguments, say [s0,t0] and [s2,t2], are swapped. When [1-t,t]
  1243.     is used for all three arguments, the result is the cubic Bezier
  1244.     curve with those data points controlling it:
  1245.  
  1246.           f(t) = F([1-t,t],[1-t,t],[1-t,t])
  1247.                =  (1-t)^3 c30 +
  1248.                  3(1-t)^2 t c21 +
  1249.                  3(1-t) t^2 c12 +
  1250.                  t^3 c03.
  1251.  
  1252.     Notice that
  1253.            F([1,0],[1,0],[1,0]) = c30,
  1254.            F([1,0],[1,0],[0,1]) = c21,
  1255.            F([1,0],[0,1],[0,1]) = c12, _
  1256.            F([0,1],[0,1],[0,1]) = c03.
  1257.  
  1258.     In other words, cij is obtained by giving F argument t's i of
  1259.     which are 0 and j of which are 1. Since F is a linear polynomial
  1260.     in each argument, we can find f(t) using a series of simple steps.
  1261.     Begin with
  1262.  
  1263.         f000 = c30, f001 = c21, f011 = c12, f111 = c03.
  1264.  
  1265.     Then compute in succession:
  1266.  
  1267.         f00t = s f000 + t f001, f01t = s f001 + t f011,
  1268.         f11t = s f011 + t f111,
  1269.         f0tt = s f00t + t f01t, f1tt = s f01t + t f11t,
  1270.         fttt = s f0tt + t f1tt.
  1271.  
  1272.     This is the de Casteljau algorithm for computing f(t) = fttt.
  1273.  
  1274.     It also has split the curve for the intervals [0..t] and [t..1].
  1275.     The control points for the first interval are f000, f00t, f0tt,
  1276.     fttt, while those for the second interval are fttt, f1tt, f11t,
  1277.     f111.
  1278.  
  1279.     If you evaluate 3 F([1-t,t],[1-t,t],[-1,1]) you will get the
  1280.     derivate of f at t. Similarly, 2*3 F([1-t,t],[-1,1],[-1,1]) gives
  1281.     the second derivative of f at t, and finally using 1*2*3
  1282.     F([-1,1],[-1,1],[-1,1]) gives the third derivative.
  1283.  
  1284.     This procedure is easily generalized to different degrees,
  1285.     triangular patches, and B-spline curves.
  1286.  
  1287.  
  1288. ----------------------------------------------------------------------
  1289. Subject 4.03: How do I find a t value at a specific point on a bezier?
  1290.  
  1291.     In general, you'll need to find t closest to your search point.
  1292.     There are a number of ways you can do this. Look at [Gems I, 607],
  1293.     there's a chapter on finding the nearest point on the bezier
  1294.     curve.  In my experience, digitizing the bezier curve is an
  1295.     acceptable method. You can also try recursively subdividing the
  1296.     curve, see if you point is in the convex hull of the control
  1297.     points, and checking is the control points are close enough to a
  1298.     linear line segment and find the nearest point on the line
  1299.     segment, using linear interpolation and keeping track of the
  1300.     subdivision level, you'll be able to find t.
  1301.  
  1302.  
  1303. ----------------------------------------------------------------------
  1304. Subject 4.04: How do I fit a bezier curve to a circle?
  1305.  
  1306.     Interestingly enough, bezier curves can approximate a circle but
  1307.     not perfectly fit a circle.
  1308.  
  1309.     Michael Goldapp, "Approximation of circular arcs by cubic
  1310.     polynomials" Computer Aided Geometric Design (#8 1991 pp.227-238)
  1311.  
  1312.     Tor Dokken and Morten Daehlen, "Good Approximations of circles by
  1313.     curvature-continuous Bezier curves" Computer Aided Geometric
  1314.     Design (#7 1990 pp. 33-41).
  1315.  
  1316.  
  1317. ----------------------------------------------------------------------
  1318. Section 5. 3D computations
  1319. ----------------------------------------------------------------------
  1320. Subject 5.01: How do I rotate a 3D point?
  1321.  
  1322.     Assuming you want to rotate vectors around the origin of your
  1323.     coordinate system. (If you want to rotate around some other point,
  1324.     subtract its coordinates from the point you are rotating, do the
  1325.     rotation, and then add back what you subtracted.) In 3-D, you need
  1326.     not only an angle, but also an axis. (In higher dimensions it gets
  1327.     much worse, very quickly.)  Actually, you need 3 independent
  1328.     numbers, and these come in a variety of flavors.  The flavor I
  1329.     recommend is unit quaternions: 4 numbers that square and add up to
  1330.     +1.  You can write these as [(x,y,z),w], with 4 real numbers, or
  1331.     [v,w], with v, a 3-D vector pointing along the axis. The concept
  1332.     of an axis is unique to 3-D. It is a line through the origin
  1333.     containing all the points which do not move during the rotation.
  1334.     So we know if we are turning forwards or back, we use a vector
  1335.     pointing out along the line. Suppose you want to use unit vector u
  1336.     as your axis, and rotate by 2t degrees.  (Yes, that's twice t.)
  1337.     Make a quaternion [u sin t, cos t]. You can use the quaternion --
  1338.     call it q -- directly on a vector v with quaternion
  1339.     multiplication, q v q^-1, or just convert the quaternion to a 3x3
  1340.     matrix M. If the components of q are {(x,y,z),w], then you want
  1341.     the matrix
  1342.  
  1343.         M = {{1-2(yy+zz),  2(xy-wz),  2(xz+wy)},
  1344.              {  2(xy+wz),1-2(xx+zz),  2(yz-wx)},
  1345.              {  2(xz-wy),  2(yz+wx),1-2(xx+yy)}}.
  1346.  
  1347.     Rotations, translations, and much more are explained in all basic
  1348.     computer graphics texts.  Quaternions are covered briefly in
  1349.     [Foley], and more extensively in several Graphics Gems, and the
  1350.     SIGGRAPH 85 proceedings.
  1351.  
  1352.     /* The following routine converts an angle and a unit axis vector
  1353.         * to a matrix, returning the corresponding unit quaternion at no
  1354.         * extra cost. It is written in such a way as to allow both fixed
  1355.         * point and floating point versions to be created by appropriate
  1356.         * definitions of FPOINT, ANGLE, VECTOR, QUAT, MATRIX, MUL, HALF,
  1357.         * TWICE, COS, SIN, ONE, and ZERO.
  1358.         * The following is an example of floating point definitions.
  1359.         #define FPOINT double
  1360.         #define ANGLE FPOINT
  1361.         #define VECTOR QUAT
  1362.         typedef struct {FPOINT x,y,z,w;} QUAT;
  1363.         enum Indices {X,Y,Z,W};
  1364.         typedef FPOINT MATRIX[4][4];
  1365.         #define MUL(a,b) ((a)*(b))
  1366.         #define HALF(a) ((a)*0.5)
  1367.         #define TWICE(a) ((a)*2.0)
  1368.         #define COS cos
  1369.         #define SIN sin
  1370.         #define ONE 1.0
  1371.         #define ZERO 0.0
  1372.     */
  1373.     QUAT MatrixFromAxisAngle(VECTOR axis, ANGLE theta, MATRIX m)
  1374.     {
  1375.         QUAT q;
  1376.         ANGLE halfTheta = HALF(theta);
  1377.         FPOINT cosHalfTheta = COS(halfTheta);
  1378.         FPOINT sinHalfTheta = SIN(halfTheta);
  1379.         FPOINT xs, ys, zs, wx, wy, wz, xx, xy, xz, yy, yz, zz;
  1380.         q.x = MUL(axis.x,sinHalfTheta);
  1381.         q.y = MUL(axis.y,sinHalfTheta);
  1382.         q.z = MUL(axis.z,sinHalfTheta);
  1383.         q.w = cosHalfTheta;
  1384.         xs = TWICE(q.x);  ys = TWICE(q.y);  zs = TWICE(q.z);
  1385.         wx = MUL(q.w,xs); wy = MUL(q.w,ys); wz = MUL(q.w,zs);
  1386.         xx = MUL(q.x,xs); xy = MUL(q.x,ys); xz = MUL(q.x,zs);
  1387.         yy = MUL(q.y,ys); yz = MUL(q.y,zs); zz = MUL(q.z,zs);
  1388.         m[X][X] = ONE - (yy + zz); m[X][Y] = xy - wz; m[X][Z] = xz + wy;
  1389.         m[Y][X] = xy + wz; m[Y][Y] = ONE - (xx + zz); m[Y][Z] = yz - wx;
  1390.         m[Z][X] = xz - wy; m[Z][Y] = yz + wx; m[Z][Z] = ONE - (xx + yy);
  1391.         /* Fill in remainder of 4x4 homogeneous transform matrix. */
  1392.         m[W][X] = m[W][Y] = m[W][Z] = m[X][W] = m[Y][W] = m[Z][W] = ZERO;
  1393.         m[W][W] = ONE;
  1394.         return (q);
  1395.     }
  1396.     /* The routine just given, MatrixFromAxisAngle, performs rotation about
  1397.         * an axis passing through the origin, so only a unit vector was needed
  1398.         * in addition to the angle. To rotate about an axis not containing the
  1399.         * origin, a point on the axis is also needed, as in the following. For
  1400.         * mathematical purity, the type POINT is used, but may be defined as:
  1401.         #define POINT VECTOR
  1402.     */
  1403.     QUAT MatrixFromAnyAxisAngle(POINT o, VECTOR axis, ANGLE theta, MATRIX m)
  1404.     {
  1405.         QUAT q;
  1406.         q = MatrixFromAxisAngle(axis,theta,m);
  1407.         m[X][W] = o.x-(MUL(m[X][X],o.x)+MUL(m[X][Y],o.y)+MUL(m[X][Z],o.z));
  1408.         m[Y][W] = o.y-(MUL(m[Y][X],o.x)+MUL(m[Y][Y],o.y)+MUL(m[Y][Z],o.z));
  1409.         m[Z][W] = o.x-(MUL(m[Z][X],o.x)+MUL(m[Z][Y],o.y)+MUL(m[Z][Z],o.z));
  1410.         return (q);
  1411.     }
  1412.     /* An axis can also be specified by a pair of points, with the direction
  1413.         * along the line assumed from the ordering of the points. Although both
  1414.         * the previous routines assumed the axis vector was unit length without
  1415.         * checking, this routine must cope with a more delicate possibility. If
  1416.         * the two points are identical, or even nearly so, the axis is unknown.
  1417.         * For now the auxiliary routine which makes a unit vector ignores that.
  1418.         * It needs definitions like the following for floating point.
  1419.         #define SQRT sqrt
  1420.         #define RECIPROCAL(a) (1.0/(a))
  1421.     */
  1422.     VECTOR Normalize(VECTOR v)
  1423.     {
  1424.         VECTOR u;
  1425.         FPOINT norm = MUL(v.x,v.x)+MUL(v.y,v.y)+MUL(v.z,v.z);
  1426.         /* Better to test for (near-)zero norm before taking reciprocal. */
  1427.         FPOINT scl = RECIPROCAL(SQRT(norm));
  1428.         u.x = MUL(v.x,scl); u.y = MUL(v.y,scl); u.z = MUL(v.z,scl);
  1429.         return (u);
  1430.     }
  1431.     QUAT MatrixFromPointsAngle(POINT o, POINT p, ANGLE theta, MATRIX m)
  1432.     {
  1433.         QUAT q;
  1434.         VECTOR diff, axis;
  1435.         diff.x = p.x-o.x; diff.y = p.y-o.y; diff.z = p.z-o.z;
  1436.         axis = Normalize(diff);
  1437.         return (MatrixFromAnyAxisAngle(o,axis,theta,m));
  1438.     }
  1439.  
  1440. ----------------------------------------------------------------------
  1441. Subject 5.02: What is ARCBALL and where is the source?
  1442.  
  1443.     Arcball is a general purpose 3-D rotation controller described by
  1444.     Ken Shoemake in the Graphics Interface '92 Proceedings.  It
  1445.     features good behavior, easy implementation, cheap execution, and
  1446.     optional axis constraints. A Macintosh demo and electronic version
  1447.     of the original paper (Microsoft Word format) may be obtained from
  1448.     ftp::/ftp.cis.upenn.edu/pub/graphics.
  1449.  
  1450.     Complete source code appears in Graphics Gems IV pp. 175-192. A
  1451.     fairly complete sketch of the code appeared in the original
  1452.     article, in Graphics Interface 92 Proceedings, available from
  1453.     Morgan Kaufmann.
  1454.  
  1455.  
  1456. ----------------------------------------------------------------------
  1457. Subject 5.03: How do I clip a polygon against a rectangle?
  1458.  
  1459.     This is the Sutherland-Hodgman algorithm, an old favorite that
  1460.     should be covered in any textbook. Any of the references listed in
  1461.     the FAQ should have it.  According to Vatti (q.v.)  "This
  1462.     [algorithm] produces degenerate edges in certain concave / self
  1463.     intersecting polygons that need to be removed as a special
  1464.     extension to the main algorithm" (though this is not a problem if
  1465.     all you are doing with the results is scan converting them.)
  1466.  
  1467.  
  1468. ----------------------------------------------------------------------
  1469. Subject 5.04: How do I clip a polygon against another polygon?
  1470.  
  1471.     Klamer Schutte, klamer@ph.tn.tudelft.nl has developed and implemented
  1472.     some code in C++ to perform clipping of two possibly concave 2-D
  1473.     polygons. A description can be found at:
  1474.     http://www.ph.tn.tudelft.nl:/People/klamer/clippoly_entry.html
  1475.     To compile the source code you will need a C++ compiler with templates,
  1476.     such as g++. The source code is available at:
  1477.     ftp://ftp.ph.tn.tudelft.nl/pub/klamer/clippoly.tar.gz
  1478.  
  1479.     References:
  1480.  
  1481.     Weiler, K. "Polygon Comparison Using a Graph Representation", SIGGRAPH 80
  1482.     pg. 10-18
  1483.  
  1484.     Vatti, Bala R. "A Generic Solution to Polygon Clipping",
  1485.     Communications of the ACM, July 1992, Vol 35, No. 7, pg. 57-63
  1486.  
  1487. ----------------------------------------------------------------------
  1488. Subject 5.05: How do I find the intersection of a line and a plane?
  1489.  
  1490.     If the plane is defined as:
  1491.  
  1492.         a*x + b*y + c*z + d = 0
  1493.  
  1494.     and the line is defined as:
  1495.  
  1496.         x = x1 + (x2 - x1)*t = x1 + i*t
  1497.         y = y1 + (y2 - y1)*t = y1 + j*t
  1498.         z = z1 + (z2 - z1)*t = z1 + k*t
  1499.  
  1500.     Then just substitute these into the plane equation. You end up
  1501.     with:
  1502.  
  1503.         t = - (a*x1 + b*y1 + c*z1 + d)/(a*i + b*j + c*k)
  1504.  
  1505.     When the denominator is zero, the line is contained in the plane 
  1506.     if the numerator is also zero (the point at t=0 satisfies the
  1507.     plane equation), otherwise the line is parallel to the plane.
  1508.  
  1509.  
  1510. ----------------------------------------------------------------------
  1511. Subject 5.06: How do I determine the intersection between a ray and a polygon
  1512.  
  1513.     First find the intersection between the ray and the plane in which
  1514.     the polygon is situated. Then see if the point of intersection is
  1515.     in the polygon.
  1516.  
  1517.     Reference:
  1518.  
  1519.     [Glassner:RayTracing]
  1520.  
  1521.  
  1522. ----------------------------------------------------------------------
  1523. Subject 5.07: How do I determine the intersection between a ray and a sphere
  1524.  
  1525.     Given a ray defined as:
  1526.  
  1527.         x = x1 + (x2 - x1)*t = x1 + i*t
  1528.         y = y1 + (y2 - y1)*t = y1 + j*t
  1529.         z = z1 + (z2 - z1)*t = z1 + k*t
  1530.  
  1531.     and a sphere defined as:
  1532.  
  1533.         (x - l)**2 + (y - m)**2 + (z - n)**2 = r**2
  1534.  
  1535.     Substituting in gives the quadratic equation:
  1536.  
  1537.         a*t**2 + b*t + c = 0
  1538.  
  1539.     where:
  1540.  
  1541.         a = i**2 + j**2 + k**2
  1542.         b = 2*i*(x1 - l) + 2*j*(y1 - m) + 2*k*(z1 - n)
  1543.         c = (x1-l)**2 + (y1-m)**2 + (z1-n)**2 - r**2;
  1544.  
  1545.     If the discriminant of this equation is less than 0, the line does
  1546.     not intersect the sphere. If it is zero, the line is tangential to
  1547.     the sphere and if it is greater than zero it intersects at two
  1548.     points. Solving the equation and substituting the values of t into
  1549.     the ray equation will give you the points.
  1550.  
  1551.     Reference:
  1552.  
  1553.     [Glassner:RayTracing]
  1554.  
  1555.  
  1556. ----------------------------------------------------------------------
  1557. Subject 5.08: How do I find the intersection of a ray and a bezier surface?
  1558.  
  1559.     Joy I.K. and Bhetanabhotla M.N., "Ray tracing parametric surfaces
  1560.     utilizing numeric techniques and ray coherence", Computer
  1561.     Graphics, 16, 1986, 279-286
  1562.  
  1563.     Joy and Bhetanabhotla is only one approach of three major method
  1564.     classes: tessellation, direct computation, and a hybrid of the
  1565.     two.  Tessellation is relatively easy (you intersect the polygons
  1566.     making up the tessellation) and has no numerical problems, but can
  1567.     be inaccurate; direct is cheap on memory, but very expensive
  1568.     computationally, and can (and usually does) suffer from precision
  1569.     problems within the root solver; hybrids try to blend the two.
  1570.  
  1571.     Reference:
  1572.  
  1573.     [Glassner:RayTracing]
  1574.  
  1575.  
  1576. ----------------------------------------------------------------------
  1577. Subject 5.09: How do I ray trace caustics?
  1578.  
  1579.     There is a discussion in [Watt:Animation], but I don't know how
  1580.     good it is.
  1581.  
  1582.     It's hard to get right.
  1583.  
  1584.     One right (but incredibly expensive) answer is:
  1585.  
  1586.     @InProceedings{mitchell-1992-illumination,
  1587.       author         = "Don P. Mitchell and Pat Hanrahan",
  1588.       title          = "Illumination From Curved Reflectors",
  1589.       year           = "1992",
  1590.       month          = "July",
  1591.       volume         = "26",
  1592.       booktitle      = "Computer Graphics (SIGGRAPH '92 Proceedings)",
  1593.       pages          = "283--291",
  1594.       keywords       = "caustics, interval arithmetic, ray tracing",
  1595.       editor         = "Edwin E. Catmull",
  1596.     }
  1597.  
  1598.     A cheat:
  1599.  
  1600.     @Article{inakage-1986-caustics,
  1601.       author         = "Masa Inakage",
  1602.       title          = "Caustics and Specular Reflection Models for
  1603.                         Spherical Objects and Lenses ",
  1604.       pages          = "379--383",
  1605.       journal        = "The Visual Computer",
  1606.       volume         = "2",
  1607.       number         = "6",
  1608.       year           = "1986",
  1609.       keywords       = "ray tracing effects",
  1610.     }
  1611.  
  1612.     very specialized:
  1613.  
  1614.     @Article{yuan-1988-gemstone,
  1615.       author         = "Ying Yuan and Tosiyasu L. Kunii and Naota
  1616.                         Inamato and Lining Sun ",
  1617.       title          = "Gemstone Fire: Adaptive Dispersive Ray Tracing
  1618.                         of Polyhedrons ",
  1619.       year           = "1988",
  1620.       month          = "November",
  1621.       journal        = "The Visual Computer",
  1622.       volume         = "4",
  1623.       number         = "5",
  1624.       pages          = "259--70",
  1625.       keywords       = "caustics",
  1626.     }
  1627.  
  1628.  
  1629. ----------------------------------------------------------------------
  1630. Subject 5.10: What is the marching cubes algorithm?
  1631.  
  1632.     The marching cubes algorithm is used in volume rendering to
  1633.     construct an isosurface from a 3D field of values.
  1634.  
  1635.     The 2D analog would be to take an image, and for each pixel, set
  1636.     it to black if the value is below some threshold, and set it to
  1637.     white if it's above the threshold.  Then smooth the jagged black
  1638.     outlines by skinning them with lines.
  1639.  
  1640.     The marching cubes algorithm tests the corner of each cube (or
  1641.     voxel) in the scalar field as being either above or below a given
  1642.     threshold.  This yields a collection of boxes with classified
  1643.     corners.  Since there are eight corners with one of two states,
  1644.     there are 256 different possible combinations for each cube.
  1645.     Then, for each cube, you replace the cube with a surface that
  1646.     meets the classification of the cube.  For example, the following
  1647.     are some 2D examples showing the cubes and their associated
  1648.     surface.
  1649.  
  1650.         - ----- +       - ----- -       - ----- +       - ----- +
  1651.         |:::'   |       |:::::::|       |::::   |       |   ':::|
  1652.         |:'     |       |:::::::|       |::::   |       |.    ':|
  1653.         |       |       |       |       |::::   |       |::.    |
  1654.         + ----- +       + ----- +       - ----- +       + ----- -
  1655.  
  1656.     The result of the marching cubes algorithm is a smooth surface
  1657.     that approximates the isosurface that is constant along a given
  1658.     threshold. This is useful for displaying a volume of oil in a
  1659.     geological volume, for example.
  1660.  
  1661.     References:
  1662.     "Marching Cubes: A High Resolution 3D Surface  Construction Algorithm",
  1663.     William E. Lorensen and Harvey E. Cline,
  1664.     Computer Graphics (Proceedings of  SIGGRAPH '87), Vol. 21, No. 4, pp. 163-169.
  1665.  
  1666.     [Watt:Animation] pp. 302-305 and 313-321
  1667.     [Schroeder]
  1668.  
  1669.  
  1670.  
  1671. ----------------------------------------------------------------------
  1672. Subject 5.11: What is the status of the patent on the "marching cubes" algorithm?
  1673.  
  1674.     United States Patent Number: 4,710,876
  1675.     Date of Patent: Dec. 1, 1987
  1676.     Inventors: Harvey E. Cline, William E. Lorensen
  1677.     Assignee: General Electric Company
  1678.     Title: "System and Method for the Display of Surface Structures Contained
  1679.             Within the Interior Region of a Solid Body"
  1680.     Filed: Jun. 5, 1985
  1681.  
  1682.  
  1683.     United States Patent Number: 4,885,688
  1684.     Date of Patent: Dec. 5, 1989
  1685.     Inventor: Carl R. Crawford
  1686.     Assignee: General Electric Company
  1687.     Title: "Minimization of Directed Points Generated in Three-Dimensional
  1688.             Dividing Cubes Method"
  1689.     Filed: Nov. 25, 1987
  1690.  
  1691.  
  1692. ----------------------------------------------------------------------
  1693. Subject 5.12: How do I do a hidden surface test (backface culling) with 3d points?
  1694.  
  1695.     Just define all points of all polygons in clockwise order.
  1696.  
  1697.             c = (x3*((z1*y2)-(y1*z2))+
  1698.                 (y3*((x1*z2)-(z1*x2))+
  1699.                 (z3*((y1*x2)-(x1*y2))+
  1700.  
  1701.     x1,y1,z1, x2,y2,z2, x3,y3,z3 = the first three points of the
  1702.     polygon.
  1703.  
  1704.     If c is positive the polygon is visible. If c is negative the
  1705.     polygon is invisible (or the other way).
  1706.  
  1707.  
  1708. ----------------------------------------------------------------------
  1709. Subject 5.13: Where can I find algorithms for 3D collision detection?
  1710.  
  1711.     Check out "proxima", from Purdue, which is a C++ library for 3D
  1712.     collision detection for arbitrary polyhedra.  It's a nice system;
  1713.     the algorithms are sophisticated, but the code is of modest size.
  1714.  
  1715.         ftp://ftp.cs.purdue.edu/pub/pse/PROX/prox9.1.tar.Z
  1716.  
  1717.     For information about the I_COLLIDE 3D collision detection system
  1718.         http://www.cs.unc.edu/~geom/I_COLLIDE.html
  1719.  
  1720.     "Fast Collision Detection of Moving Convex Polyhedra", Rich Rabbitz,
  1721.     Graphics Gems IV, pages 83-109, includes source in C.
  1722.  
  1723. ----------------------------------------------------------------------
  1724. Subject 5.14: How do I perform basic viewing in 3d?
  1725.  
  1726.     We describe the shape and position of objects using numbers,
  1727.     usually (x,y,z) coordinates. For example, the corners of a cube
  1728.     might be {(0,0,0), (1,0,0), (1,1,0), (0,1,0), (0,0,1), (1,0,1),
  1729.     (1,1,1), (0,1,1)}. A deep understanding of what we are saying with
  1730.     these numbers requires mathematical study, but I will try to keep
  1731.     this simple. At the least, we must understand that we have
  1732.     designated some point in space as the origin--coordinates
  1733.     (0,0,0)--and marked off lines in 3 mutually perpendicular
  1734.     directions using equally spaced units to give us (x,y,z) values.
  1735.     It might be helpful to know if we are using 1 to mean 1 foot, 1
  1736.     meter, or 1 parsec; the numbers alone do not tell us.
  1737.  
  1738.     A picture on a screen is two steps removed from the 3D world it
  1739.     depicts. First, it is a 2D projection; and second, it is a finite
  1740.     resolution approximation to the infinitely precise projection. I
  1741.     will ignore the approximation (sampling) for now. To know what the
  1742.     projection looks like, we need to know where our viewpoint is, and
  1743.     where the plane of the projection is, both in the 3D world. Think
  1744.     of it as looking out a window into a scene. As artists discovered
  1745.     some 500 years ago, each point in the world appears to be at a
  1746.     point on the window. If you move your head or look out a different
  1747.     window, everything changes. When the mathematicians understood
  1748.     what the artists were doing, they invented perspective geometry.
  1749.  
  1750.     If your viewpoint is at the origin--(0,0,0)--and the window sits
  1751.     parallel to the x-y plane but at z=1, projection is no more than
  1752.     (x,y,z) in the world appears at (x/z,y/z,1) on the plane. Distant
  1753.     points will have large z values, causing them to shrink in the
  1754.     picture. That's perspective.
  1755.  
  1756.     The trick is to take an arbitrary viewpoint and plane, and
  1757.     transform the world so we have the simple viewing situation.
  1758.     There are two steps: move the viewpoint to the origin, then move
  1759.     the viewplane to the z=1 plane. If the viewpoint is at (vx,vy,vz),
  1760.     transform every point by the translation (x,y,z) -->
  1761.     (x-vx,y-vy,z-vz). This includes the viewpoint and the viewplane.
  1762.     Now we need to rotate so that the z axis points straight at the
  1763.     viewplane, then scale so it is 1 unit away.
  1764.  
  1765.     After all this, we may find ourselves looking out upside- down. It
  1766.     is traditional to specify some direction in the world or viewplane
  1767.     as "up", and rotate so the positive y axis points that way (as
  1768.     nearly as possible if it's a world vector). Finally, we have acted
  1769.     so far as if the window was the entire plane instead of a limited
  1770.     portal. A final shift and scale transforms coordinates in the
  1771.     plane to coordinates on the screen, so that a rectangular region
  1772.     of interest (our "window") in the plane fills a rectangular region
  1773.     of the screen (our "canvas" if you like).
  1774.  
  1775.     I have left out details of how you define and perform the rotation
  1776.     of the viewplane, but I'm sure someone else will be happy to
  1777.     supply those if there is demand. It requires knowing how to
  1778.     describe a plane, and how to rotate vectors to line up. Neither is
  1779.     difficult, but this is already using a lot of net space. One
  1780.     further practical difficulty is the need to clip away parts of the
  1781.     world behind us, so -(x,y,z) doesn't pop up at (x/z,y/z,1).
  1782.     (Notice the mathematics of projection alone would allow that!) But
  1783.     all the viewing transformations can be done using translation,
  1784.     rotation, scale, and a final perspective divide. If a 4x4
  1785.     homogeneous matrix is used, it can represent everything needed,
  1786.     which saves a lot of work.
  1787.  
  1788. ----------------------------------------------------------------------
  1789. Subject 5.15: How Do I optimize a 3D polygon mesh
  1790.  
  1791.     References:
  1792.     "Mesh Optimization" Hoppe, DeRose Duchamp, McDonald, Stuetzle,
  1793.      ACM COMPUTER GRAPHICS Proceedings, Annual Conference Series, 1993.
  1794.  
  1795.     "Re-Tiling Polygonal Surfaces",
  1796.      Greg Turk, ACM Computer Graphics, 26, 2, July 1992
  1797.  
  1798.     "Decimation of Triangle Meshes", Schroeder, Zarge, Lorensen,
  1799.     ACM Computer Graphics, 26, 2 July 1992
  1800.  
  1801.     "Simplification of ObjectsRendered by Polygonal Approximations",
  1802.     Michael J. DeHaemer, Jr. and Michael J. Zyda, Computer & Graphics,
  1803.     Vol. 15, No. 2, 1991, Great Britain: Pergamon Press, pp. 175-184.
  1804.  
  1805.  
  1806. ----------------------------------------------------------------------
  1807. Subject 5.16: How can I perform volume rendering?
  1808.  
  1809.     Two principal methods can be used:
  1810.     - Ray casting or front-to-back, where the volume is behind the
  1811.       projection plane. A ray is projected from each point in the projection
  1812.       plane through the volume. The ray accumulates the properties of each
  1813.       voxel it passes through.
  1814.     - Object order or back-to-front, where the projection plane is behind
  1815.       the volume. Each slice of the volume is projected on the projection
  1816.       plane, from the farest plane to the nearest plane.
  1817.  
  1818.     You can also use the marching-cubes algorithm, if the extraction of
  1819.     surfaces from the data set is easy to do (see Subject 5.10).
  1820.  
  1821.     Here is one algorithm to do front-to-back volume rendering:
  1822.  
  1823.     Set up a projection plane as a plane tangent to a sphere that encloses 
  1824.     the volume. From each pixel of the projection plane, cast a ray 
  1825.     through the volume by using a Bresenham 3D algorithm.
  1826.     The ray accumulates properties from each voxel intersected, stopping
  1827.     when the ray exits the volume. The pixel value on
  1828.     the projection plane determines the final color of the ray.
  1829.  
  1830.     For unshaded images (i.e., without gradient and light computations),
  1831.     if     C  is the ray color            t  the ray transparency
  1832.         C' the new ray color           t' the new ray transparency
  1833.         Cv the voxel color             tv the voxel transparency
  1834.     then:
  1835.         C' = C + t*Cv       and        t' = t * tv
  1836.     with initial values: C = 0.0 and t = 1.0
  1837.  
  1838.     An alternate version: instead of C' = C + t*Cv , use :
  1839.         C' = C + t*Cv*(1-tv)^p     with p a float variable.
  1840.     Sometimes this gives the best results.
  1841.     When the ray has accumulated transparency, if it becomes negligible
  1842.     (e.g., t<0.1), the process can stop and proceed to the next ray.
  1843.  
  1844.     References:
  1845.  
  1846.     Bresenham 3D:
  1847.       - http://www.sct.gu.edu.au/~anthony/info/graphics/bresenham.procs
  1848.       - [Gems IV] p. 366
  1849.     Volume rendering:
  1850.       - [Watt:Animation] pp. 297-321
  1851.       - IEEE Computer Graphics and application
  1852.         Vol. 10, Nb. 2, March 1990 - pp. 24-53
  1853.       - "Volume Visualization"
  1854.         Arie Kaufman - Ed. IEEE Computer Society Press Tutorial
  1855.       - "Efficient Ray Tracing of Volume Data"
  1856.         Marc Levoy - ACM Transactions on Graphics, Vol. 9, Nb 3, July 1990
  1857.  
  1858. ----------------------------------------------------------------------
  1859. Subject 5.17: Where can I get the spline description of the famous teapot etc.?
  1860.  
  1861.     See the Standard Procedural Databases software, whose official
  1862.     distribution site is 
  1863.         http://www.acm.org/tog/resources/SPD/
  1864.     This database contains much useful 3D code, including spline surface
  1865.     tessellation, for the teapot.
  1866.  
  1867. ----------------------------------------------------------------------
  1868. Subject 5.18: How can the distance between two lines in space be computed?
  1869.  
  1870.     The following is robust C code from Seth Teller that computes the 
  1871.     "points of closest approach" on two 3D lines.  It also classifies 
  1872.     the lines as parallel, intersecting, or (the generic case) skew.
  1873.  
  1874.     // computes pB ON line B closest to line A
  1875.     // computes pA ON line A closest to line B
  1876.     // return: 0 if parallel; 1 if coincident; 2 if generic (i.e., skew)
  1877.     int
  1878.     line_line_closest_points3d (
  1879.         POINT *pA, POINT *pB,            // computed points
  1880.         const POINT *a, const VECTOR *adir,        // line A, point-normal form
  1881.         const POINT *b, const VECTOR *bdir )    // line B, point-normal form
  1882.     {
  1883.     static VECTOR Cdir, *cdir = &Cdir;
  1884.     static PLANE Ac, *ac = &Ac, Bc, *bc = &Bc;
  1885.     
  1886.         // connecting line is perpendicular to both
  1887.         vcross ( cdir, adir, bdir );
  1888.     
  1889.         // check for near-parallel lines
  1890.         if ( !vnorm( cdir ) )   {
  1891.             *pA = *a;    // all points are closest
  1892.             *pB = *b;
  1893.             return 0;    // degenerate: lines parallel
  1894.             }
  1895.     
  1896.         // form plane containing line A, parallel to cdir
  1897.         plane_from_two_vectors_and_point ( ac, cdir, adir, a );
  1898.     
  1899.         // form plane containing line B, parallel to cdir
  1900.         plane_from_two_vectors_and_point ( bc, cdir, bdir, b );
  1901.     
  1902.         // closest point on A is line A ^ bc
  1903.         intersect_line_plane ( pA, a, adir, bc );
  1904.     
  1905.         // closest point on B is line B ^ ac
  1906.         intersect_line_plane ( pB, b, bdir, ac );
  1907.     
  1908.         // distinguish intersecting, skew lines
  1909.         if ( edist( pA, pB ) < 1.0E-5F )
  1910.             return 1;     // coincident: lines intersect
  1911.         else
  1912.             return 2;     // distinct: lines skew
  1913.     }
  1914.  
  1915. ----------------------------------------------------------------------
  1916. Section 6. Geometric Structures and Mathematics
  1917. ----------------------------------------------------------------------
  1918. Subject 6.01: Where can I get source for Voronoi/Delaunay triangulation?
  1919.  
  1920.     For 2-d Delaunay triangulation, try Shewchuk's triangle program.  It
  1921.     includes options for constrained triangulation and quality mesh
  1922.     generation.  It uses exact arithmetic.
  1923.  
  1924.     The Delaunay triangulation is equivalent to computing the convex hull
  1925.     of the points lifted to a paraboloid.  For n-d Delaunay triangulation
  1926.     try Clarkson's hull program (exact arithmetic) or Barber and Huhdanpaa's
  1927.     Qhull program (floating point arithmetic).  The hull program also
  1928.     computes Voronoi volumes and alpha shapes.  The Qhull program also
  1929.     computes 2-d Voronoi diagrams and n-d Voronoi vertices.  The output of
  1930.     both programs may be visualized with Geomview.
  1931.  
  1932.     There are many other codes for Delaunay triangulation and Voronoi
  1933.     diagrams.  See Amenta's list of computational geometry software.
  1934.  
  1935.     The Delaunay triangulation satisfies the following property: the
  1936.     circumcircle of each triangle is empty.  The Voronoi diagram is the
  1937.     closest-point map, i.e., each Voronoi cell identifies the points that
  1938.     are closest to an input site.  The Voronoi diagram is the dual of
  1939.     the Delaunay triangulation.  Both structures are defined for general
  1940.     dimension.  Delaunay triangulation is an important part of mesh
  1941.     generation.
  1942.  
  1943.     References:
  1944.  
  1945.     Amenta:   http://www.geom.umn.edu/software/cglist
  1946.  
  1947.     Barber &  http://www.geom.umn.edu/locate/qhull
  1948.     Huhdanpaa ftp://geom.umn.edu/pub/software/qhull.tar.Z
  1949.  
  1950.     Clarkson: http://cm.bell-labs.com/netlib/voronoi/hull.html
  1951.               ftp://cm.bell-labs.com/netlib/voronoi/hull.shar.Z
  1952.  
  1953.     Geomview: http://www.geom.umn.edu/locate/geomview
  1954.               ftp://geom.umn.edu/pub/software/geomview/
  1955.  
  1956.     Shewchuk: http://www.cs.cmu.edu/~quake/triangle.html
  1957.               ftp://cm.bell-labs.com/netlib/voronoi/triangle.shar.Z
  1958.  
  1959.  
  1960.     [O' Rourke] pp. 168-204
  1961.  
  1962.     [Preparata & Shamos] pp. 204-225
  1963.  
  1964.     Chew, L. P. 1987. "Constrained Delaunay Triangulations," Proc. Third
  1965.     Annual ACM Symposium on Computational Geometry.
  1966.  
  1967.     Chew, L. P. 1989. "Constrained Delaunay Triangulations," Algorithmica
  1968.     4:97-108. (UPDATED VERSION OF CHEW 1987.)
  1969.  
  1970.     Fang, T-P. and L. A. Piegl. 1994. "Algorithm for Constrained Delaunay
  1971.     Triangulation," The Visual Computer 10:255-265. (RECOMMENDED!)
  1972.  
  1973.     Frey, W. H. 1987. "Selective Refinement: A New Strategy for Automatic
  1974.     Node Placement in Graded Triangular Meshes," International Journal for
  1975.     Numerical Methods in Engineering 24:2183-2200.
  1976.  
  1977.     Guibas, L. and J. Stolfi. 1985. "Primitives for the Manipulation of
  1978.     General Subdivisions and the Computation of Voronoi Diagrams," ACM
  1979.     Transactions on Graphics 4(2):74-123.
  1980.  
  1981.     Karasick, M., D. Lieber, and L. R. Nackman. 1991. "Efficient Delaunay
  1982.     Triangulation Using Rational Arithmetic," ACM Transactions on Graphics
  1983.     10(1):71-91.
  1984.  
  1985.     Lischinski, D. 1994. "Incremental Delaunay Triangulation," Graphics
  1986.     Gems IV, P. S. Heckbert, Ed. Cambridge, MA: Academic Press Professional.
  1987.     (INCLUDES C++ SOURCE CODE -- THANK YOU, DANI!)
  1988.  
  1989.     [Okabe]
  1990.  
  1991.     Schuierer, S. 1989. "Delaunay Triangulation and the Radiosity
  1992.     Approach," Proc. Eurographics '89, W. Hansmann, F. R. A. Hopgood, and
  1993.     W. Strasser, Eds. Elsevier Science Publishers, 345-353.
  1994.  
  1995.     Subramanian, G., V. V. S. Raveendra, and M. G. Kamath. 1994. "Robust
  1996.     Boundary Triangulation and Delaunay Triangulation of Arbitrary
  1997.     Triangular Domains," International Journal for Numerical Methods in
  1998.     Engineering 37(10):1779-1789.
  1999.  
  2000.     Watson, D. F. and G. M. Philip. 1984. "Survey: Systematic
  2001.     Triangulations," Computer Vision, Graphics, and Image Processing
  2002.     26:217-223.
  2003.  
  2004.  
  2005.  
  2006. ----------------------------------------------------------------------
  2007. Subject 6.02: Where do I get source for convex hull?
  2008.  
  2009.     For n-d convex hulls, try Clarkson's hull program (exact arithmetic)
  2010.     or Barber and Huhdanpaa's Qhull program (floating point arithmetic).
  2011.     Qhull handles numeric precision problems by merging facets. The output
  2012.     of both programs may be visualized with Geomview.
  2013.  
  2014.     In higher dimensions, the number of facets may be much smaller than
  2015.     the number of lower-dimensional features.  When this is the case,
  2016.     Fukuda's cdd program is much faster than Qhull or hull.
  2017.  
  2018.     There are many other codes for convex hulls.  See Amenta's list of
  2019.     computational geometry software.
  2020.  
  2021.     References:
  2022.  
  2023.     Amenta:   http://www.geom.umn.edu/software/cglist/
  2024.  
  2025.     Barber &  http://www.geom.umn.edu/locate/qhull
  2026.     Huhdanpaa ftp://geom.umn.edu/pub/software/qhull.tar.Z
  2027.  
  2028.     Clarkson: http://cm.bell-labs.com/netlib/voronoi/hull.html
  2029.               ftp://cm.bell-labs.com/netlib/voronoi/hull.shar.Z
  2030.  
  2031.     Geomview: http://www.geom.umn.edu/locate/geomview
  2032.               ftp://geom.umn.edu/pub/software/geomview/
  2033.  
  2034.     Fukuda:   ftp://ifor13.ethz.ch/pub/fukuda/cdd/
  2035.  
  2036.  
  2037.     [O' Rourke] pp. 70-167
  2038.     C code for Graham's algorithm on p.80-96.
  2039.     Three-dimensional convex hull discussed in Chapter 4 (p.113-67).
  2040.     C code for the incremental algorithm on p.130-60.
  2041.  
  2042.     [Preparata & Shamos] pp. 95-184
  2043.  
  2044.  
  2045. ----------------------------------------------------------------------
  2046. Subject 6.03: Where do I get source for halfspace intersection?
  2047.  
  2048.     For n-d halfspace intersection, try Fukuda's cdd program or Barber
  2049.     and Huhdanpaa's Qhull program.  Both use floating point arithmetic.
  2050.     Fukuda includes code for exact arithmetic.  Qhull handles numeric
  2051.     precision problems by merging facets.
  2052.  
  2053.     Qhull computes halfspace intersection by computing a convex hull.
  2054.     The intersection of halfspaces about the origin is equivalent to the
  2055.     convex hull of the halfspace coefficients divided by their offsets.
  2056.  
  2057.     References:
  2058.  
  2059.     Barber &  http://www.geom.umn.edu/locate/qhull
  2060.     Huhdanpaa ftp://geom.umn.edu/pub/software/qhull.tar.Z
  2061.  
  2062.     Fukuda:   ftp://ifor13.ethz.ch/pub/fukuda/cdd/
  2063.  
  2064.     [Preparata & Shamos] pp. 315-320
  2065.  
  2066.  
  2067.  
  2068. ----------------------------------------------------------------------
  2069. Subject 6.04: What are barycentric coordinates?
  2070.  
  2071.         Let p1, p2, p3 be the three vertices (corners) of a closed 
  2072.     triangle T (in 2D or 3D or any dimension).  Let t1, t2, t3 be real 
  2073.     numbers that sum to 1, with each between 0 and 1:  t1 + t2 + t3 = 1,
  2074.     0 <= ti <= 1.  Then the point p = t1*p1 + t2*p2 + t3*p3 lies in
  2075.     the plane of T and is inside T.  The numbers (t1,t2,t3) are called the
  2076.     barycentric coordinates of p with respect to T. They uniquely identify
  2077.     p.  They can be viewed as masses placed at the vertices whose
  2078.     center of gravity is p.
  2079.         For example, let p1=(0,0), p2=(1,0), p3=(3,2).  The
  2080.     barycentric coordinates (1/2,0,1/2) specify the point
  2081.     p = (0,0)/2 + 0*(1,0) + (3,2)/2 = (3/2,1), the midpoint of the p1-p3 
  2082.     edge.
  2083.         If p is joined to the three vertices, T is partitioned
  2084.     into three triangles.  Call them T1, T2, T3, with Ti not incident
  2085.     to pi.  The areas of these triangles Ti are proportional to the
  2086.     barycentric coordinates ti of p.  
  2087.     
  2088.     Reference:
  2089.     [Coxeter, Intro. to Geometry, p.217].
  2090.  
  2091. ----------------------------------------------------------------------
  2092. Subject 6.05: How can I generate a random point inside a triangle?
  2093.  
  2094.         Use barycentric coordinates (see item 53) .  Let A, B, C be the
  2095.     three vertices of your triangle.  Any point P inside can be expressed
  2096.     uniquely as P = aA + bB + cC, where a+b+c=1 and a,b,c are each >= 0.
  2097.     Knowing a and b permits you to calculate c=1-a-b.  So if you can
  2098.     generate two random numbers a and b, each in [0,1], such that
  2099.     their sum <=1, you've got a random point in your triangle.
  2100.         Generate random a and b independently and uniformly in [0,1] 
  2101.     (just divide the standard C rand() by its max value to get such a 
  2102.     random number.) If a+b>1, replace a by 1-a, b by 1-b.  Let c=1-a-b.  
  2103.     Then aA + bB + cC is uniformly distributed in triangle ABC: the reflection
  2104.     step a=1-a; b=1-b gives a point (a,b) uniformly distributed in the triangle
  2105.     (0,0)(1,0)(0,1), which is then mapped affinely to ABC.
  2106.     Now you have barycentric coordinates a,b,c.  Compute your point 
  2107.     P = aA + bB + cC.
  2108.  
  2109.     Reference: [Gems I], Turk, pp. 24-28.
  2110.  
  2111. ----------------------------------------------------------------------
  2112. Subject 6.06: How do I evenly distribute N points on (tesselate) a sphere?
  2113.     
  2114.     "Evenly distributed" doesn't have a single definition.  There is a
  2115.     sense in which only the five Platonic solids achieve regular
  2116.     tesselations, as they are the only ones whose faces are regular
  2117.     and equal, with each vertex incident to the same number of faces.
  2118.     But generally "even distribution" focusses not so much on the
  2119.     induced tesselation, as it does on the distances and arrangement
  2120.     of the points/vertices.  For example, eight points can be placed
  2121.     on the sphere further away from one another than is achieved by
  2122.     the vertices of an inscribed cube: start with an inscribed cube,
  2123.     twist the top face 45 degrees about the north pole, and then
  2124.     move the top and bottom points along the surface towards the equator 
  2125.     a bit.
  2126.  
  2127.     The various definitions of "evenly distributed" lead into moderately 
  2128.     complex mathematics. This topic happens to be a FAQ on sci.math as well 
  2129.     as on comp.graphics.algorithms; a much more extensive and rigorous 
  2130.     discussion written by Dave Rusin can be found at:
  2131.     http://www.math.niu.edu/~rusin/papers/known-math/spheres/sphere.faq
  2132.  
  2133.     A simple method of tesselating the sphere is repeated subdivision. An
  2134.     example starts with a unit octahedron. At each stage, every triangle in
  2135.     the tesselation is divided into 4 smaller triangles by creating 3 new
  2136.     vertices halfway along the edges. The new vertices are normalized,
  2137.     "pushing" them out to lie on the sphere. After N steps of subdivision,
  2138.     there will be 8 * 4^N triangles in the tesselation.
  2139.  
  2140.     A simple example of tesselation by subdivision is available at
  2141.        ftp://ftp.cs.unc.edu/pub/users/leech/sphere.c
  2142.  
  2143.     One frequently used definition of "evenness" is a distribution that 
  2144.     minimizes a 1/r potential energy function of all the points, so that in 
  2145.     a global sense points are as "far away" from each other as possible. 
  2146.     Starting from an arbitrary distribution, we can either use numerical 
  2147.     minimization algorithms or point repulsion, in which all the points 
  2148.     are considered to repel each other according to a 1/r^2 force law and 
  2149.     dynamics are simulated. The algorithm is run until some convergence 
  2150.     criterion is satisfied, and the resulting distribution is our approximation.
  2151.     
  2152.     Jon Leech developed code to do just this.  It is available at
  2153.     ftp://ftp.cs.unc.edu/pub/users/leech/points.tar.gz.
  2154.     See his README file for more information.  His distribution includes
  2155.     sample output files for various n < 300, which may be used off-the-shelf
  2156.     if that is all you need.
  2157.  
  2158. ----------------------------------------------------------------------
  2159. Subject 6.07: What are coordinates for the vertices of an icosohedron?
  2160.  
  2161.     Data on various polyhedra is available at
  2162.     http://cm.bell-labs.com/netlib/polyhedra/index.html
  2163.     For the icosahedron, the twelve vertices are:
  2164.  
  2165.       (+- 1, 0, +-t), (0, +-t, +-1), and (+-t, +-1, 0)
  2166.  
  2167.     where t = (sqrt(5)-1)/2, the golden ratio.
  2168.     Reference: "Beyond the Third Dimension" by Banchoff, p.168.
  2169.     
  2170.     
  2171. ----------------------------------------------------------------------
  2172. Subject 6.08: How do I generate random points on the surface of a sphere?
  2173.  
  2174.     The trig method.  This method works only in 3-space, but it is
  2175.     very fast.  It depends on the slightly counterintuitive fact (see
  2176.     proof below) that each of the three coordinates is uniformly
  2177.     distributed on [-1,1] (but the three are not independent,
  2178.     obviously).  Therefore, it suffices to choose one axis (Z, say)
  2179.     and generate a uniformly distributed value on that axis.  This
  2180.     constrains the chosen point to lie on a circle parallel to the
  2181.     X-Y plane, and the obvious trig method may be used to obtain the
  2182.     remaining coordinates.
  2183.     
  2184.         (a) Choose z uniformly distributed in [-1,1].
  2185.         (b) Choose t uniformly distributed on [0, 2*pi).
  2186.         (c) Let r = sqrt(1-z^2).
  2187.         (d) Let x = r * cos(t).
  2188.         (e) Let y = r * sin(t).
  2189.     
  2190.     This method uses uniform deviates (faster to generate than normal
  2191.     deviates), and no set of coordinates is ever rejected.  
  2192.     
  2193.     Here is a proof of correctness for the fact that the z-coordinate is
  2194.     uniformly distributed.  The proof also works for the x- and y-
  2195.     coordinates, but note that this works only in 3-space.
  2196.     
  2197.     The area of a surface of revolution in 3-space is given by
  2198.     
  2199.         A = 2 * pi * int_a^b f(x) * sqrt(1 + [f'(x}]^2) dx
  2200.     
  2201.     Consider a zone of a sphere of radius R.  Since we are integrating in
  2202.     the z direction, we have
  2203.     
  2204.         f(z) = sqrt(R^2 - z^2)
  2205.         f'(z) = -z / sqrt(R^2-z^2)
  2206.     
  2207.         1 + [f'(z)]^2 = r^2 / (R^2-z^2)
  2208.     
  2209.         A = 2 * pi * int_a^b sqrt(R^2-z^2) * R/sqrt(R^2-z^2) dz
  2210.           = 2 * pi * R int_a^b dz
  2211.           = 2 * pi * R * (b-a)
  2212.           = 2 * pi * R * h, 
  2213.           
  2214.     where h = b-a is the vertical height of the zone.  Notice how the integrand
  2215.     reduces to a constant.  The density is therefore uniform.
  2216.  
  2217. ----------------------------------------------------------------------
  2218. Section 7. Contributors
  2219. ----------------------------------------------------------------------
  2220. Subject 7.01: How can you contribute to this FAQ?
  2221.  
  2222.     Send email to orourke@cs.smith.edu with your suggestions, possible
  2223.     topics, corrections, or pointers to information.  
  2224.  
  2225. ----------------------------------------------------------------------
  2226. |Subject 7.02: Contributors.  Who made this all possible.
  2227.  
  2228.     Jens Alfke <jens_alfke@powertalk.apple.com>
  2229. |   Leen Ammeraal <ammeraal@ibk.fnt.hvu.nl>
  2230.     Scott Anguish <sanguish@digifix.com>
  2231.     Brad Barber <barber@geom.umn.edu, barber@tiac.net>
  2232.     Paul Bourke <pdbourke@ccu1.auckland.ac.nz>
  2233.     Andrew Bromage <bromage@mundil.cs.mu.OZ.AU>
  2234.     Brent Burley <brent@aimla.com>
  2235.     R. Kevin Burton <engr@waun.tdsnet.com>
  2236.     Ken Clarkson <clarkson@research.att.com>
  2237.     Martin Dillon <martind@mv.pi.csiro.au>
  2238.     Thomas Djafari <frogger@micronet.fr>
  2239.     Dave Eberly <eberly@cs.unc.edu>
  2240.     John Eickemeyer <johne@iti.gov.sg>
  2241.     John E (Edward) Ellis <je_ellis@ccmail.pnl.gov>
  2242.     Ata Etemadi <Ata.Etemadi@team17.com>
  2243.     Eric Haines <erich@eye.com>
  2244.     Luiz Henrique de Figueiredo <lhf@visgraf.impa.br><lhf@csgrs6k4.uwaterloo.ca>
  2245.     Andrew Fitzgibbon <andrewfg@aifh.ed.ac.uk>
  2246.     David N. Fogel <fogel@geog.ucsb.edu>
  2247.     Sandy Harris <sandy@storm.ca>
  2248.     Steve Hollasch <hollasch@kgc.com>
  2249.     Craig Kolb <cek@Princeton.EDU>
  2250.     Steve Lamont <spl@szechuan.ucsd.edu>
  2251.     Jon Leech <leech@cs.unc.edu>
  2252.     Sum Lin <slin@esri.com>
  2253.     Sebastien Loisel <zed@sgi.com>
  2254.     Fritz Lott <fritz@riverside.MR.Net>
  2255.     Marc Christopher Martin <mcm@post5.tele.dk>
  2256.     John McNamara <jmn.ac@fusilla.abanet.it>
  2257.     Samuel Murphy <sammy@icarus.smds.com>
  2258.     Aaron Orenstein <aorenste@atitech.com>
  2259.     Joseph O'Rourke <orourke@cs.smith.edu>
  2260.     Samuel S. Paik <paik@mlo.dec.com>
  2261.     Christian von Roques <roques@pond.sub.org>
  2262.     Dave Seaman <ags@seaman.cc.purdue.edu>
  2263.     Klamer Schutte <klamer@ph.tn.tudelft.nl>
  2264.     Jeff Somers <jsomers@tiac.net>
  2265.     Ken Shoemake <shoemake@graphics.cis.upenn.edu>
  2266.     Jon Stone <jdstone@ingr.com>
  2267.     Seth Teller <seth@larch.lcs.mit.edu>
  2268.     Yael "YoeL" Touboul <Yael.Touboul@ifp.fr>
  2269.     Anson Tsao <ansont@hookup.net>
  2270.     Jim Ward <jfw@radix.net>
  2271.     Jason Weiler <weilej@rpi.edu>
  2272.     Karsten Weiss <karsten@addx.stgt.sub.org>
  2273.  
  2274.     Previous Editors:
  2275.     Jon Stone <jdstone@ingr.com>
  2276.     Anson Tsao <ansont@hookup.net>
  2277.  
  2278.